Egy város úthálózata kereszteződésekből és ezeket a kereszteződéseket összekötő egyirányú utcákból (élekből) áll. Minden utca pontosan két különböző kereszteződést kapcsol össze. Minden kereszteződéspárt legfeljebb egy egyirányú utca kapcsol össze. Az úthálózatnak megvan az a tulajdonsága, hogy minden kereszteződés minden másikból elérhető a fenti egyirányú utcákon. A városi tanács elhatározta, hogy az utcákat felújítja, s emiatt az éppen javítottat lezárja. Egyszerre csak egyet! A javítási munkák azokkal az utcákkal kezdődnek, amelyek lezárásával az úthálózat összefüggősége megmarad.
Feladat:
Írj programot, amely az úthálózat adatainak beolvasását követően megadja, hogy mely utcák zárhatók le az összefüggőség megtartása mellett.
Bemenet:
A bemeneti állomány több tesztesetet tartalmazhat, amelyek számát az állomány első sorába írt egész szám határozza meg. A tesztesetek első sora két egészet, az N és az M értékét tartalmazza. Az N (3<=N<=500) a kereszteződések számát, az M (3<=M<=50000) az utcák számát szabja meg. A kereszteződéseket 1-től N-ig sorszámozzuk, így kerülnek azonosításra. A következő M sor az X és az Y (1<=X, Y<=N) egészeket tartalmazza, amelyek az X-ből Y-ba vezető egyirányú utcát határozzák meg.
Kimenet:
A kimeneti állomány minden tesztesetre azokat az utakat tartalmazza, amelyek az összefüggőség megsértése nélkül lezárhatók. Minden sor egy utat tartalmaz. Ha nincs ilyen út, akkor egy üres sort kell ideírni. Minden tesztesetre adott válasz a 0 0 párral zárul.
Példa:
|
roads.in |
roads.out |
|
2 |
2 4 0 0 |
(ACM SZTE csapatverseny 2000)