Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | drumuri.in, drumuri.out | Sursă | Finala GInfo 2005 |
| Autor | Cosmin Silvestru Negruseri, Leonard Crestez | Adăugată de | |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Drumuri
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
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.in | drumuri.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 | 0 |
