== include(page="template/taskheader" task_id="ulei") ==
Poveste şi cerinţă...
Dezamăgit de afacerea Siragul, Lunasorab s-a gândit să plece în vacanţă la Paris. A decis să încerce lucruri noi, cum ar fi vizitarea unei galerii de artă. Galeria are mai multe tipuri de tablouri, însă cele care il interesează cel mai mult pe Lunasorab sunt cele în ulei (de mic copil i-a plăcut sa schimbe uleiul la maşină). Galeria este formată din $N$ camere care comunică între ele prin $M$ coridoare, iar tablourile în ulei se găsesc numai pe coridoare, câte unul pe fiecare coridor. Fiecare tablou este pictat cu un tip anume de ulei. Cum nu umblă cu jumătăti de masură, Lunasorab ar vrea să vadă toate tablourile în ulei. Fiind prima lui vizită la muzeu, el doreşte să vadă fiecare tablou exact o dată (în momentul în care trece printr-un coridor Lunasorb vede tabloul care se află acolo). De asemenea, pentru a nu se plictisi, el nu vrea sa vadă două tablouri consecutive care folosesc acelaşi tip de ulei şi nu vrea să termine vizita în muzeu cu un tablou pictat cu acelaşi tip de ulei ca primul tablou văzut. El nu poate să treacă dintr-o cameră în alta decât prin coridorul care le uneşte şi va trece prin fiecare coridor exact o dată. De asemenea, secvenţa de coridoare parcursă nu conţine $2$ tablouri consecutive pictate în acelaşi tip de ulei. În plus, tipul primului tablou văzut trebuie să fie diferit de cel al ultimului tablou vizitat. Vizita începe şi se termină din aceeaşi cameră.
De aceea, el vă cere ajutorul, promiţându-vă o parte din profitul următoarei sale afaceri. Pentru a fi sigur ca nu îl păcăliţi, el vă va furniza mai multe planuri de galerii, alegând la sfârşit pe cel care-i place cel mai mult.
h2. Cerinta
Dându-se planul galeriei, găsiţi o secvenţă de coridoare prin care să treacă Lunasorb.
h2. Date de intrare
Fişierul de intrare $ulei.in$ ...
Fişierul de intrare $ulei.in$ va conţine pe prima linie numărul natural $T$, reprezentând numărul de teste. Pe urmatoarele linii vor urrma $T$ teste, descrise în continuare.
Fiecare test este format din $M$ + $1$ linii. Prima linie va conţine $N$ si $M$, reprezentând numărul de camere precum şi numărul de coridoare. Pe urmatoarele $M$ linii se vor afla coridoarele, unul pe linie, date sub forma $i$ $j$ $t$, semnificând faptul că există un coridor de la camera $i$ la camera $j$, conţinând un tablou care foloseste tipul $t$ de ulei. Coridoarele sunt bidirecţionale, iar între aceeaşi pereche de camere poate exista cel mult un coridor.
h2. Date de ieşire
În fişierul de ieşire $ulei.out$ ...
Fişierul de ieşire $ulei.out$ va conţine $T$ linii. Pe fiecare linie se găseşte o secvenţă de $M$ + $1$ de numere naturale separate prin câte un spaţiu, reprezentând numerele camerelor în ordinea vizitării.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 1 ≤ $T$ ≤ 5
* 1 ≤ $N$ ≤ 15.000
* 1 ≤ $M$ ≤ 100.000
* Nu va exista coridor de la o cameră la ea însăşi
* Pe testele folosite la evaluare va exista mereu soluţie
* Tipurile de ulei vor fi între $1$ si $15.000$
* Pentru {$20$}% din teste vor fi doar $2$ tipuri de ulei
h2. Exemplu
table(example). |_. ulei.in |_. ulei.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
3 3
1 2 1
2 3 2
3 1 3
| 1 2 3 1
|
h3. Explicaţie
...
Lunasorab începe vizita în camera $1$, continuând cu camerele $2$ si $3$, revenind în final în camera $1$. Astfel, el a vizitat toate tablourile şi nu s-a plictisit.
== include(page="template/taskfooter" task_id="ulei") ==
