e-olymp
Змагання

ADA Classes - Depth First Search

Двокольоровість

У 1976 році "Теорема чотирьох фарб" була доведена при допомозі комп'ютера. Ця теорема стверджує, що довільна карта може бути розфарбована з використанням лише чотирьох фарб таким чином, що жодна з областей не буде зафарбована з використанням тих же кольорів, що і в сусідніх областях.

Вам пропонується розв'язати подібну задачу, але простішу. Необхідно вияснити, чи є заданий довільний зв'язний граф двокольоровим. Тобто чи можна його вершинам призначити кольори (усього є два кольори) таким чином, щоб жодні дві суміжні вершини не мали однаковий колір. Для спрощення задачі можна припустити, що:

  • граф не має петель.
  • граф неорієнтовний. Тобто якщо вершина a зв'язана з вершиною b, то і b зв'язана з a.
  • граф зв'язний. Тобто завжди існує хоча б один шлях з довільної вершини у довільну іншу.

Вхідні дані

Складається з декількох тестів. Кожен тест починається з рядка, який містить кількість вершин n (0n1000). Другий рядок містить кількість ребер l (1l250000). Після цього йде l рядків, кожен з яких містить два числа, які вказують на ребро між двома вершинами, які воно з'єднує. Вершини у графі буде позначено числом a (1an). Останній тест містить n = 0 та не обробляється.

Вихідні дані

Вияснити, чи можна зробити вхідний граф двокольоровим і вивести відповідне повідомлення, як показано у прикладі.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
3
1 2
2 3
3 1
9
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
0
Вихідні дані #1
NOT BICOLOURABLE.
BICOLOURABLE.