arce

Asupra unui graf neorientat se dorește efectuarea unei operații de transformare a muchiilor în arce. Practic toate muchiile din graf vor fi orientate ținându-se cont de faptul că la finalul operației oricare vârf al grafului trebuie să aibă gradul extern par.

Cerință

Scrieți un program care să realizeze o orientare corectă a muchiilor, dacă aceasta este posibilă.

Date de intrare

Fisierul arce.in are următorul format:
-pe prima linie un număr natural n reprezentand de noduri ale grafului;
-pe fiecare dintre următoarele linii se afla cate o pereche de numere naturale i j (numere cuprinse intre 1 si n) cu semnificația între nodurile i și j există muchie.

Date de ieșire

Fisierul arce.out va conține pe fiecare linie cate o pereche de numere i j cu semnificatia : muchia [i, j] se transformă în arcul (i,j) (arc orientat de la i spre j). Ordinea în care se vor scrie arcele nu contează. Dacă operația de orientare nu este realizabilă atunci se va scrie cuvantul Imposibil

Restricții

N <= 5000
Numărul de muchii ale grafului <=100000.

Exemple

arce.in

Conținutul fisierului arce.out poate fi:

arce.in

arce.out

4
1 2
2 3
3 4
4 1

 1 2
1 4
3 2
3 4

3
1 2
2 3
3 1

Imposibil

Timp maxim de executie/test: 0.25 secunde

Dana Lica
Colegiul National "I.L.Caragiale" - Ploiesti
Contact:danal182001@yahoo.com