Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Dvidalis grafas

Neorientuotasis grafas vadinamas dvidaliu, jei jo viršūnių aibę galima išskaidyti į dvi nesikertančias aibes taip, kad kiekvienos jo briaunos galai (viršūnės) priklausytų skirtingoms aibėms.

(Sąlygą galima suformuluoti ir vaizdžiau: grafas yra dvidalis, jei jo viršūnes galima nuspalvinti dviem spalvomis taip, kad jokios gretimos (sujungtos briauna) viršūnės nebūtų nuspalvintos ta pačia spalva.)

Parašykite programą, kuri nustatytų, ar duotasis grafas yra dvidalis.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti du sveikieji skaičiai N ir M - grafo viršūnių ir briaunų skaičiai (1\\leN\\le1000; 0\\leM\\le10000). Grafo viršūnės sunumeruotos skaičiais nuo 1 iki N. Sekančiose M eilučių pateiktos skaičių ui ir vi poros (1\\leu_i, vi\\leN), žyminčios, jog viršūnes u_i ir v_i grafe jungia briauna.

Rezultatai

Pirmoje rezultatų failo eilutėje turi būti įrašytas žodis TAIP, jei grafas yra dvidalis, ir žodis NE, priešingu atveju.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3 3
1 2
1 3
2 3
 
NE
 
6 8
1 2
1 4
1 5
2 3
2 6
3 4
3 5
4 6
 
TAIP
 img 
1000 0
 
TAIP