== include(page="template/taskheader" task_id="balanta") ==
Chernel Camatarul are probleme. A primit de la un client $N$ monede identice presupuse a fi din aur, dar el banuieste ca exact una dintre acestea este falsa. Chernel stie ca moneda falsa este ori mai grea, ori mai usoara decat cele din aur, toate celelalte avand mase egale. Pentru a verifica, el foloseste o balanta cu ajutorul careia executa $M$ cantariri. La fiecare cantarire pune un numar egal de monede pe cele doua talere si isi noteaza rezultatul. Din pacate, Chernel actioneaza destul de haotic, iar la final nu stie daca in urma cantaririlor poate determina cu precizie moneda falsa.
Ajutati-l sa afle raspunsul!
Poveste si cerinta...
h2. Date de intrare
De pe prima linie a fisierului de intrare se citesc doua numere intregi $N$ si $M$. Urmeaza $M$ linii, fiecare fiind descrisa in felul urmator: un numar $k$, reprezentand numarul de monede asezat pe fiecare din cele doua talere ale balantei, $k$ numere intregi intre $1$ si $N$ reprezentand monedele asezate pe talerul stang, alte $k$ numere intregi intre $1$ si $N$ reprezentand monedele asezate pe talerul drept, alaturi de un numar $r$ din multimea ${0, 1, 2}$. $r$ indica rezultatul cantaririi, acesta fiind $0$ daca balanta ramane in echilibru, $1$ daca talerul stang este mai greu decat cel drept, respectiv $2$ daca talerul drept este mai greu decat cel stang.
...
h2. Date de iesire
Prima linie a fisierului de iesire contine un numar intreg intre $1$ si $N$, reprezentand moneda falsa in cazul in care aceasta se poate determina cu precizie, respectiv $0$ in cazul in care cantaririle lui Chernel nu au fost suficiente pentru a gasi moneda respectiva.
...
h2. Restrictii
* $1 ≤ N, M ≤ 1024$
* $... ≤ ...$
h2. Exemplu
table(example). |_. balanta.in |_. balanta.out |
| 8 3
4 1 2 3 4 5 6 7 8 1
1 1 2 0
1 3 4 2 | 4 |
| 4 2
2 1 2 3 4 2
1 2 3 2
| $0$ |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="balanta") ==
