Úloha: nepostradatelný datový kanál

Jistá nejmenovaná banka má ve světě N poboček označených čísly od 0 do N-1. Mezi pobočkami jsou vybudovány zabezpečené datové kanály pro výměnu informací o klientech a účtech mezi pobočkami. Každý datový kanál spojuje vždy dvojici poboček. Všechny kanály jsou komunikačně obousměrné. Mezi některými dvojicemi poboček přímý datový kanál nevede, ale z každé pobočky je možné se spojit s využitím existujících propojení datovými kanály s libovolnou jinou pobočkou (třeba i více různými způsoby). Jednotlivé datové kanály jsou mezi sebou propojeny pouze v pobočkách.

Datový kanál nazveme nepostradatelný, pokud by se jeho poškozením nebo zničením úplně přerušilo datové spojení mezi některou dvojicí poboček a tím by banka nebyla schopna udržovat jednotná data o svých klientech a bankovních účtech.

Napište program, který vyhledá a vypíše všechny nepostradatelné datové kanály. Vstupem programu je počet poboček N a dále seznam všech datových kanálů vedoucích mezi pobočkami. Každý datový kanál je zadán dvojicí čísel poboček, mezi nimiž vede.

Vstup

Na prvním řádku vstupu bude počet poboček banky. Na dalších řádcích budou vždy dvojice poboček odděleny mezerou. Každá dvojice představuje ty pobočky, které jsou mezi sebou propojeny datovým kanálem. Pobočky jsou číslovány od 0. Celý vstup je ukončen řádkem "0 0". Předpokládejte, že na vstupu je korektně zadaná souvislá síť poboček banky.

Výstup

Na každém řádku výstupu je vypsaná dvojice poboček oddělené mezerou. Každá dvojice představuje přímý nepostradatelný kanál mezi dvěma pobočkami. Na pořadí poboček v popisu kanálu a pořadí nepostradatelných kanálů nezáleží. Celý výstup je ukončen řádkem "0 0".


Níže uvádíme tři příklady, třetí se špatně zobrazuje, má okolo 300000 uzlů a cca 450000 hran.

Příklad 1:

Vstup:

8
0 3
1 3
2 3
4 5
4 6
4 7
3 4
0 1
1 2
5 6
6 7
0 0

Výstup:

3 4
0 0

Příklad 2:

Vstup:

23
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
21 22
20 22
19 21
18 21
17 20
16 20
15 19
14 19
13 18
12 18
11 17
10 17
9 16
8 16
0 0

Výstup:

2 6
2 7
0 2
19 14
19 15
21 19
16 20
0 3
0 0

Příklad 3:

Vstup

Výstup

Příklad 4:
Diamant bez špičky, menší velikost

Vstup

Výstup