Fişierul intrare/ieşire:	afterparty.in, afterparty.out	Sursă	ONIS 2015, Runda Finala
Autor	Mihai Calancea	Adăugată de	ONIS2015 •ONIS2015
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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ă, nu-i aşa?.

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ă des - şi zice că tu probabil nu ştii să găseşti un cuplaj perfect. Pe deplin revoltat de această ipoteză, îi dai mândru replica: "Boss, eu pot să determin TOATE cuplajele perfecte". Te calmezi un pic şi realizezi că de fapt nu ştii să faci asta, ba chiar nu ştii nici să numeri câte cuplaje perfecte sunt.

Totuşi, dacă te străduieşti, crezi că poţi să-i spui paritatea numărului de cuplaje perfecte.

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.

Date de ieşire

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.

Restricţii

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100
• 0 ≤ M ≤ N * (N - 1) / 2
• Se numeşte cuplaj perfect într-un graf bipratit o mulţime de muchii ale grafului cu proprietatea că fiecare nod este capătul exact unei singure muchii.

Exemplu

Explicaţie

În primul exemplu există un unic cuplaj perfect.
În al doilea exemplu, deşi Doxuta este foarte bine conectat cu toate celebrităţile concursului, nu se poate forma niciun cuplaj perfect.

Cum se trimit solutii?