== include(page="template/taskheader" task_id="moneda") ==

Cunoasteti cu totii problema "clasica" a celor $N$ monede (numerotate de la $1$ la $N$), dintre care una este diferita (mai grea sau mai usoara). Pentru a identifica moneda diferita, aveti la dispozitie o balanta cu $2$ talere, cu care puteti efectua cantariri. O cantarire consta in amplasarea a aceluiasi numar de monede pe fiecare din cele $2$ talere (stang si drept). Rezultatul unei cantariri indica daca monedele (sau monezile) de pe cele $2$ talere au aceeasi greutate, daca cele de pe talerul stang sunt mai grele, sau daca cele de pe talerul drept sunt mai grele. Gigel a efectuat $M$ cantariri in vederea identificarii monezii diferite. Totusi, dupa ce a efectuat cele $M$ cantariri, el nu stie cum sa mai continue, astfel ca va cere ajutorul. Gigel ar vrea sa stie care este numarul minim suplimentar de cantariri ce mai trebuie efectuate pentru a identifica moneda diferita (cunoscand cantaririle efectuate in prealabil de Gigel, impreuna cu rezultatul acestora).

Cunoasteti cu totii problema "clasica" a celor $N$ monede (numerotate de la $1$ la $N$), dintre care una este diferita (mai grea sau mai usoara). Pentru a identifica moneda diferita (si a stii daca este mai grea sau mai usoara decat celelalte monezi), aveti la dispozitie o balanta cu $2$ talere, cu care puteti efectua cantariri. O cantarire consta in amplasarea a aceluiasi numar de monezi pe fiecare din cele $2$ talere (stang si drept). Rezultatul unei cantariri indica daca monezile de pe cele $2$ talere au aceeasi greutate, daca cele de pe talerul stang sunt mai grele, sau daca cele de pe talerul drept sunt mai grele. Gigel a efectuat $M$ cantariri in vederea identificarii monezii diferite. Totusi, dupa ce a efectuat cele $M$ cantariri, el nu stie cum sa mai continue, astfel ca va cere ajutorul. Gigel ar vrea sa stie care este numarul minim suplimentar de cantariri ce mai trebuie efectuate in cel mai rau caz pentru a identifica moneda diferita, precum si de a sti daca este mai grea sau mai usoara decat celelalte monezi (cunoscand cantaririle efectuate in prealabil de Gigel, impreuna cu rezultatul acestora).

h2. Date de intrare

Fişierul de intrare $moneda.in$ contine pe prima linie numerele $N$ si $T$. In continuare, vor fi descrise $T$ teste, fiecare test corespunzand unui caz cu acelasi numar $N$ de monezi. Prima linie ce descrie un test contine numarul $M$ de cantariri efectuate de Gigel. Urmatoarele $M$ linii descriu cantaririle. O linie ce descrie o cantarire are urmatorul format. Primul numar de pe linie este numarul $K$ de monezi ce au fost amplasate pe fiecare din cele $2$ talere ale balantei. Urmatoarele $K$ numere de pe linie contin numerele monezilor amplasate pe talerul stang, iar urmatoarele $K$ numere contin numerele monezilor amplasate pe talerul drept. Ultimul numar de pe linie descrie rezultatul cantariri: $0$ - daca greutatile monezilor de pe cele $2$ talere sunt egale; $-1$ - daca monezile de pe talerul stang sunt mai grele; $1$ - daca monezile de pe talerul drept sunt mai grele.

Fişierul de intrare $moneda.in$ contine pe prima linie numerele $N$ si $T$. In continuare, vor fi descrise $T$ teste, fiecare test corespunzand unui caz cu acelasi numar $N$ de monezi. Prima linie ce descrie un test contine numarul $M$ de cantariri efectuate de Gigel. Urmatoarele $M$ linii descriu cantaririle. O linie ce descrie o cantarire are urmatorul format. Primul numar de pe linie este numarul $K$ de monezi ce au fost amplasate pe fiecare din cele $2$ talere ale balantei. Urmatoarele $K$ numere de pe linie contin numerele monezilor amplasate pe talerul stang, iar urmatoarele $K$ numere contin numerele monezilor amplasate pe talerul drept. Ultimul numar de pe linie descrie rezultatul cantaririi:
 
* $0$ - daca greutatile monezilor de pe cele $2$ talere sunt egale
* $-1$ - daca monezile de pe talerul stang sunt mai grele
* $1$ - daca monezile de pe talerul drept sunt mai grele.
 
Toate numerele de pe aceeasi linie sunt separate intre ele prin cate un spatiu.

h2. Date de ieşire

În fişierul de ieşire $moneda.out$ veti afisa $T$ linii, cate una pentru fiecare test dat in fisierul de intrare (in ordinea in care sunt date testele). Pe linia corespunzatoare unui test veti afisa un singur numar, reprezentand numarul minim de cantariri suplimentare necesare pentru a identifica moneda diferita.

În fişierul de ieşire $moneda.out$ veti afisa $T$ linii, cate una pentru fiecare test dat in fisierul de intrare (in ordinea in care sunt date testele). Pe linia corespunzatoare unui test veti afisa un singur numar, reprezentand numarul minim de cantariri suplimentare necesare in cel mai rau caz pentru a identifica moneda diferita (si a sti daca este mai grea sau mai usoara decat celelalte monezi).

h2. Restricţii

* $1 ≤ N ≤ 60$

* $3 ≤ N ≤ 60$

* $1 ≤ T ≤ 10.000$
* $0 ≤ M ≤ 10$
* $1 ≤ K ≤ N/2$

* Se garanteaza ca raspunsurile la cele $M$ intrebari puse de Gigel nu sunt contradictorii.

h2. Exemplu

0
0
2

|
|10 20
1
4 10 5 9 3 6 2 8 7 -1
1
3 3 2 7 9 6 8 0
1
3 3 8 10 6 5 4 0
1
3 5 2 4 9 8 3 1
2
5 2 10 9 7 6 1 3 5 4 8 1
4 9 3 10 2 4 6 5 1 0
2
3 2 6 5 3 1 10 0
5 4 8 3 7 1 2 6 5 10 9 -1
1
4 7 1 4 9 2 3 6 10 1
4
3 6 2 3 1 7 5 0
4 7 2 9 10 5 4 1 8 -1
5 9 4 8 2 1 5 10 7 6 3 1
3 6 4 8 5 9 1 1
3
5 9 2 10 8 3 1 6 7 5 4 1
4 3 5 7 2 9 10 8 6 -1
5 1 4 10 2 9 6 3 7 8 5 1
1
3 9 3 6 5 10 2 -1
2
4 4 10 7 8 6 9 3 5 -1
3 2 7 4 6 3 9 -1
2
3 2 9 7 3 5 10 0
4 6 1 4 7 5 10 3 9 -1
3
3 2 3 6 8 5 10 1
4 1 8 9 4 3 6 10 5 -1
4 3 2 4 6 7 5 1 8 1
0
3
5 8 6 1 5 10 7 9 3 2 4 -1
4 5 9 10 3 1 8 7 6 0
3 8 4 9 5 10 3 0
1
3 5 6 8 10 9 4 -1
2
5 8 2 6 5 1 3 7 4 9 10 1
3 4 9 6 8 1 10 0
3
5 8 9 4 2 1 5 6 7 3 10 -1
3 7 3 8 6 2 4 0
3 10 6 3 7 4 5 0
4
4 10 3 4 8 2 6 9 5 -1
4 2 6 10 1 7 5 4 9 -1
4 2 4 5 8 7 6 3 9 1
5 1 4 2 6 3 8 5 9 7 10 -1
1
5 1 8 10 6 4 5 2 9 3 7 1
|2
2
2
2
1
2
2
1
2
2
2
1
1
3
0
2
2
1
0
3

|
h3. Explicaţie