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
Dana
Lica
Colegiul National "I.L.Caragiale"
- Ploiesti
Contact:danal182001@yahoo.com