==Include(page="template/taskheader" task_id="drumuri")==
 
==Include(page="template/raw")==
 
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.
 
h2. 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.
 
h2. 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.
 
h2. Restrictii
 
. 1 <= n <= 10.000
 
. 1 <= m <= 30.000
 
 
 
Exemple
 
drumuri.in drumuri.out
 
5 6 1
 
1 2 3 1 2
 
2 3 3 4 5
 
3 1 2 3 5
 
3 4
 
4 5
 
5 3
 
 
 
drumuri.in drumuri.out
 
3 3 0
 
1 2
 
2 3

==Include(page="template/taskheader" task_id="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.
 
h2. 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.
 
h2. 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$.
 
h2. Restrictii
 
* $1 ≤ n ≤ 10.000$
* $1 ≤ m ≤ 30.000$
 
 
h2. Exemple
 
table(example). |_. 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  |
 
==Include(page="template/taskfooter" task_id="drumuri")==

3 1
==Include(page="template/taskfooter" task_id="drumuri")==

418