- Pradinių duomenų failas:
- dvidalis.in
- Rezultatų failas:
- dvidalis.out
- Laiko apribojimas:
- 1 s.
- Atminties apribojimas:
- 16 Mb.
Užduotis
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 <= N <= 1000; 0 <= M <= 10 000). Grafo viršūnės sunumeruotos skaičiais nuo 1 iki N. Sekančiose M eilučių pateiktos skaičių \(u_{i}\) ir \(v_{i}\) poros (1 <= \(u_{i}\), \(v_{i}\) <= N), ž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 |  |
| 1000 0 | TAIP |
|