Fişierul intrare/ieşire:neconex.in, neconex.outSursăLot Sibiu 2011
AutorCosmin-Mihai Tutunaru, Pit-Rada VasileAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.85 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Neconex

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.

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

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

Exemplu

neconex.inneconex.out
3
4 1
1 2
5 2
2 1
4 5
7 0
1
0
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content