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 pentru al i-lea graf şi 0 în caz contrar.
Restricţii
• 1 ≤ T ≤ 31
• 2 ≤ N ≤ 20 000
• 0 ≤ M ≤ 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.