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

Eşti la after-party-ul organizat după concurs. Stai la bar şi conversezi cu prietenul tău, Eudoxiu, zis Doxuţă. Eşti uşor frustrat fiindcă echipa lui Doxuţă te-a făcut astăzi, deşi tu ştii că a avut noroc, că testele au fost slabe şi că până la urmă o victorie la penalizare nu e victorie adevărată. Discuţia merge înspre a observa oamenii din club şi relaţiile dintre ei. Până acum aţi observat că sunt $N$ persoane şi $M$ relaţii de curtoaz

Eşti la after-party-ul organizat după concurs. Stai la bar şi conversezi cu prietenul tău, Eudoxiu, zis Doxuţă. Eşti uşor frustrat fiindcă echipa lui Doxuţă te-a făcut astăzi, deşi tu ştii că a avut noroc, că testele au fost slabe şi că până la urmă o victorie la penalizare nu e victorie adevărată, nu-i aşa?.

h2. Date de intrare

Discuţia merge înspre a observa persoanele din club şi relaţiile dintre ele. Până acum aţi observat că sunt $N$ persoane şi $M$ relaţii de curtoazie între ele, relaţii care sunt bidirecţionale (aici am părăsit realitatea). Observaţi şi că persoanele pot fi împărţite în două mulţimi $A$ şi $B$, astfel încât persoanele din $A$ curtează/sunt curtate doar de persoane din mulţimea $B$. Doxuţă nu scapă ocazia şi se laudă că el poate determina dacă există cuplaj perfect între cele $N$ persoane. Mai mult, "te ia la caterincă" -un termen suburban de care abuzează- şi zice că tu probabil nu ştii să găseşti un cuplaj perfect. Pe deplin revoltat de această ipoteză, i-o întorci mândru "Boss, eu pot să determin TOATE cuplajele perfecte". Te calmezi un pic şi realizezi că de fapt nu ştii să faci asta, ba nu ştii nici să numeri câte cuplaje perfecte sunt.
 
Totuşi, dacă te gândeşti un pic, parcă poţi să-i spui paritatea numărului de cuplaje perfecte.

Fişierul de intrare $afterparty.in$ ...

h2. Date de intrare
Fişierul de intrare $afterparty.in$ va conţine pe prima sa linie numărul de teste $T$. Urmează $T$ teste, fiecare respectând următoarea structură: pe prima linie se află numerele $N$ şi $M$, semnificând numărul de persoane şi numărul de relaţii de curtoazie. Urmează $M$ linii fiecare conţinând o pereche de nume $X Y$, semnificând faptul că $X$ şi $Y$ se curtează reciproc. $X$ şi $Y$ vor fi formate din litere mici şi mari ale alfabetului englez şi vor avea o lungime maximă de $20$ de caractere.
 

h2. Date de ieşire

În fişierul de ieşire $afterparty.out$ ...

În fişierul de ieşire $afterparty.out$ va conţine $T$ linii, fiecare conţinând răspunsul pentru testul corespunzător: mesajul "Par", dacă numărul de cuplaje perfecte este par, respectiv "Impar" altfel.

h2. Restricţii