Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bazaconii.in, bazaconii.out | Sursă | Algoritmiada 2009, Runda 2 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bazaconii
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.
Date de intrare
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.
Date de ieşire
Î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.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 10 000
- Pentru fiecare triplet i j k, 1 ≤ i, j ≤ N si 0 ≤ k ≤ 1 000 000 000
Exemplu
| bazaconii.in | bazaconii.out |
|---|---|
| 2 2 2 1 2 3 1 2 1 2 1 1 2 1 | -1 0 1 |
Explicaţie
...
