neconex

Cerință

Pe internet circulă de ceva timp un joc nou numit "Neconex" care poate fi jucat de două persoane folosind un graf care nu este conex. Cei doi jucători mută alternativ. Printr-o mutare se înţelege adăugarea unei muchii între două noduri distincte între care nu există deja muchie. Pierde jucătorul la care se realizează conexitatea, adică toate nodurile grafului aparţin aceleiaşi componente conexe.

În loc să se pregătească pentru “Lotul Naţional de Informatică”, Ţirbi şi Birţi joacă acest joc, iar Ţirbi mută mereu primul. Deoarece ambii sunt destul de buni la algoritmică, ei joacă optim.

Cerință

Dându-se $T$ grafuri, să se spună dacă Ţirbi are strategie de câştig sau nu pentru fiecare graf în parte.

Date de intrare

Fişierul de intrare neconex.in conţine pe prima linie numărul $T$, iar pe următoarele linii va fi descris fiecare graf în parte. Descrierea fiecărui graf începe cu o linie ce conţine $N$ şi $M$ (reprezentând numărul de noduri şi numărul de muchii ale grafului), iar pe următoarele $M$ linii se află câte două numere naturale $A$ şi $B$ reprezentând faptul că există o muchie între nodurile $A$ şi $B$.

Date de ieșire

Fişierul de ieşire neconex.out conţine $T$ linii, câte una pentru fiecare graf din fişierul de intrare. Pe linia $i$ se va afla $1$ dacă Ţirbi are strategie de câştig şi $0$ în caz contrar.

Restricții și precizări

• $1 \leq T \leq 31$
• $2 \leq N \leq 20 \ 000$
• $0 \leq M \leq 20 \ 000$
• Se garantează că niciun graf din fişierul de intrare nu este conex.
• Prin joc optim se înţelege faptul că ambii jucători vor încerca să câştige.
• Pentru $15\%$ din teste $M = 0$.
• Pentru $30\%$ din teste $T \leq 13$ şi $N \leq 20$.
• Pentru $60\%$ din teste $N \leq 1 \ 000$.

Exemplu

neconex.in

3
4 1
1 2
5 2
2 1
4 5
7 0

neconex.out

1
0
1