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

Poveste si cerinta...

Nargy si Fumeanu joaca un joc pe un graf orientat aciclic cu $N$ noduri si $M$ muchii. In acest graf exista $K$ pioni in noduri. Fiecare jucator poate muta, cand ii vine randul, oricati pioni din nodurile lor in noduri adiacente. Cel care nu mai poate muta atunci cand ii vine randul pierde partida. La inceputul unui joc, prima mutare o face jucatorul Nargy.
Dandu-se mai multe configuratii de pioni, sa se determine cine castiga jocul, daca ambii jucatori joaca optim.

h2. Date de intrare

Fisierul de intrare $pioni.in$ ...

Fisierul de intrare $pioni.in$ contine pe prima linie numerele $T N M$ separate prin spatii. Urmatoarele $M$ linii vor contine cate doua numere naturale $a b$ cu semnificatia ca exista muchie de la $a$ la $b$. Urmatoarele $T$ linii vor descrie configuratii de pioni astfel: primul numar din linie va fi $K$ si va fi urmat de inca $K$ numere naturale reprezentand nodurile in care se afla pioni.

h2. Date de iesire

In fisierul de iesire $pioni.out$ ...

In fisierul de iesire $pioni.out$ se vor scrie urmatoarele pentru fiecare din cele $T$ configuratii:
 
* numele jucatorului care castiga pe o linie (Nargy sau Fumeanu)
* daca Nargy poate castiga se va descrie si o prima mutare pe care o poate face astfel incat sa castige: se va scrie $nr$ reprezentand numarul de pioni pe care ii muta la prima mutare, urmat de $nr$ perechi de numere $a b$ cu semnificatia ca se muta un pion din nodul $a$ in nodul $b$

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 5$
* $1 ≤ N ≤ 20.000$
* $1 ≤ M ≤ 50.000$
* $1 ≤ K ≤ 30.000$
* Pot exista mai multi pioni in acelasi nod

h2. Exemplu
table(example). |_. pioni.in |_. pioni.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 4 3
2 1
3 1
4 3
3 2 2 3
2 1 4
| Nargy
3 2 1 2 1 3 1
Fumeanu

|
h3. Explicatie

...

In prima configuratie Nargy poate castiga mutand toti pionii din $2$ si $3$ in $1$. Astfel, Fumeanu nu va mai putea muta.
In a doua configuratie singurul pion care se poate muta este cel din $4$ ({$1$} nu are noduri adiacente). Asadar, Nargy este fortat sa mute din $4$ in $3$, Fumeanu va muta apoi din $3$ in $1$, iar Nargy va pierde.

== include(page="template/taskfooter" task_id="pioni") ==