== include(page="template/taskheader" task_id="bazaconii") ==
Poveste şi cerinţă...
Andrei si Maria sunt doi copii care se tin mereu de bazaconii. Ultima bazaconie facuta de cei doi a fost sa piarda o foaie pe care era scris un sir de $N$ numere naturale. Ei nu isi mai amintesc acum ce numere erau in sir, dar isi amintesc in schimb $M$ relatii de forma $i j k$ cu semnificatia ca suma xor a numerelor din sir aflate pe pozitiile $i$ si $j$ este $k$. Copiii au incercat sa reconstituie sirul initial pe baza acestor relatii, dar nu au reusit si de aceea va cer voua ajutorul. Ei isi mai doresc ca in cazul in care exista mai multe siruri de numere care satisfac toate relatiile sa stie doar sirul cel mai mic din punct de vedere lexicografic.
h2. Date de intrare
Fişierul de intrare $bazaconii.in$ ...
Fişierul de intrare $bazaconii.in$ contine pe prima linie numarul $T$, reprezentand numarul de teste ce urmeaza a fi descrise. In continuare urmeaza cele $T$ teste, pe prima linie aflandu-se $N$ si $M$, separate de un singur spatiu, avand semnificatia din enunt. Urmeaza apoi $M$ linii, pe fiecare aflandu-se trei numere naturale separate de un singur spatiu, $i$, $j$ si $k$, avand semnificatia din enunt.
h2. Date de ieşire
În fişierul de ieşire $bazaconii.out$ ...
În fişierul de ieşire $bazaconii.out$ se vor afisa $T$ linii, pe linia $i$ aflandu-se raspunsul pentru al $i$-lea test din fisierul de intrare. Daca nu exista niciun sir care sa respecte conditiile se va afisa doar numarul $-1$, altfel se vor afisa $N$ numere naturale separate de un singur spatiu, reprezentand cel mai mic sir din punct de vedere lexicografic care respecta toate conditiile.
h2. Restricţii
* $... ≤ ... ≤ ...$
* Pentru $20%$ din teste $N ≤ 7$ si se garanteaza ca solutia optima va avea toate valorile mai mici sau egale decat $20$
* $1 ≤ T ≤ 10$
* $1 ≤ N, M ≤ 10 000$
* Pentru fiecare triplet $i j k$, $1 ≤ i, j ≤ N$ si $0 ≤ k ≤ 2 000 000 000$
* Pentru a obtine suma xor a doua numere naturale se scriu numerele in reprezentare binara, apoi fiecare bit al rezultatului va fi $1$ numai daca bitii corespunzatori ai celor doua numere sunt diferiti, altfel va fi $0$. Exemplu: $0 xor 1 = 1$, $1 xor 0 = 1$, $1001 xor 1100 = 0101$. In C/C++ exista operatorul "$^$" care face aceasta operatie, iar in pascal exista operatorul "$xor$".
* Un sir $X$ este mai mic din punct de vedere lexicografic decat un sir $Y$ daca exista un $k$ astfel incat $X{~i~}=Y{~i~}$ pentru orice $i<k$ si $X{~k~}<Y{~k~}$
h2. Exemplu
table(example). |_. bazaconii.in |_. bazaconii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
2 2
1 2 3
1 2 1
2 1
1 2 1
| -1
0 1
|
h3. Explicaţie
...
Pentru al doilea test o solutie posibila era si $1 0$, dar sirul $0 1$ este cel mai mic din punct de vedere lexicografic.
== include(page="template/taskfooter" task_id="bazaconii") ==
