neconex

Neconex

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

Poveste şi 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.

h2. Date de intrare

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

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$.

h2. Date de ieşire

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

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.

h2. 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.
* Pentru $15%$ din teste $M = 0$.
* Pentru $30%$ din teste $T ≤ 13$ şi $N ≤ 20$.
* Pentru $60%$ din teste $N ≤ 1 000$.

h2. Exemplu
table(example). |_. neconex.in |_. neconex.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="neconex") ==

5654