Alinuţa şi Bogdan se joacă pe un graf neorientat astfel:
- Jucătorul care mută primul alege un vârf oarecare al grafului.
- La fiecare dintre următoarele mutări cel care este la mutare alege un vârf al grafului care nu a mai fost ales la mutările precedente şi care este adiacent cu ultimul vârf ales.
- Jucătorii mută alternativ.
- Pierde jucătorul care nu mai poate face nici o mutare.
- Alinuţa face prima mutare.
Cerinţă
Ştiind că cei doi jucători joacă optim şi că graful neorientat pe care cei doi se joacă nu are cicluri de lungime impară se cere să se determine câştigătorul jocului pentru un graf dat.
Date de intrare
Fişierul de intrare graphgame.in
conţine pe prima linie numărul natural T reprezentând numărul de teste ce vor urma. Urmează descrierea celor T teste. Pe prima linie a fiecărui test se vor afla 2 numere naturale N şi M reprezentând numărul de vârfuri, respectiv numărul de muchii ale grafului pe care cei doi se joacă. Vârfurile grafului sunt numerotate cu numere naturale distincte de la 1 la N. Pe fiecare dintre următoarele M linii se vor afla 2 numere naturale distincte x şi y (1<=x,y<=N) reprezentând o muchie în graf.
Date de ieşire
Fişierul de ieşire graphgame.out
va conţine T linii. Pe linia i (1<=i<=T) se va afişa răspunsul pentru testul i. Mai exact se va afişa 1 dacă Alinuţa câştigă şi 2 în caz contrar.
Restricţii
1 <= T <= 10
1 <= N <= 1000
1 <= M <= 3000
Între oricare 2 vârfuri va exista cel mult o muchie.