Fişierul intrare/ieşire:drumuri.in, drumuri.outSursăFinala GInfo 2005
AutorCosmin Silvestru Negruseri, Leonard CrestezAdăugată de
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Drumuri

Intr-o tara exista n orase intre care exista un numar total de m drumuri pe care se poate circula in ambele sensuri. Intre oricare doua orase poate exista cel mult un drum.

Din nefericire, in aceasta tara rata criminalitatii este foarte mare si au loc o multime de jafuri "la drumul mare". Din acest motiv, conducatorii tarii au luat decizia de a amplasa paznici pe fiecare drum.

In tara respectiva a fost introdusa cota unica de impozitare, motiv pentru care fondurile de la buget sunt limitate. Pentru a reduce cheltuielile, fiecare paznic va trebui sa pazeasca doua drumuri.

Un paznic poate pazi numai doua drumuri care se intersecteaza si se doreste ca fiecare strada sa fie pazita de exact un paznic si fiecare paznic sa pazeasca exact doua drumuri. Reteaua de drumuri este construita in asa fel incat de la un oras se poate ajunge la oricare altul.

Va trebui sa verificati daca tara poate fi pazita astfel incat sa fie respectate dorintele liderilor si, daca este posibil, sa stabiliti drumurile pazite de fiecare paznic.

Date de intrare

Pe prima linie a fisierului de intrare drumuri.in se afla doua numere naturale n si m, reprezentand numarul oraselor, respectiv numarul drumurilor; aceste numere sunt separate printr-un spatiu. Urmatoarele m linii contin cate doua numere intregi, separate printr-un spatiu, reprezentand doua orase intre care se afla un drum.

Date de iesire

In fisierul de iesire drumuri.out se va scrie pe prima linie valoarea 1 daca exista o solutie, sau valoarea 0 daca problema nu are solutie. Daca problema are solutie atunci pe urmatoarele m / 2 linii vor fi scrise cate trei numere intregi; astfel, pe linia i + 1 vor fi scrise numerele x, y si z, separate printr-un spatiu, cu semnificatia: paznicul i pazeste drumul dintre orasele x si y, precum si drumul dintre orasele y si z.

Restrictii

  • 1 ≤ n ≤ 10.000
  • 1 ≤ m ≤ 30.000

Exemple

drumuri.indrumuri.out
5 6
1 2
2 3
3 1
3 4
4 5
5 3
1
3 1 2
3 4 5
2 3 5
3 3
1 2
2 3
3 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content