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

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

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

• граф не має петель.

• граф неорієнтовний. Тобто якщо вершина $a$ зв'язана з вершиною $b$, то і $b$ зв'язана з $a$.

• граф зв'язний. Тобто завжди існує хоча б один шлях з довільної вершини у довільну іншу.

Вхідні дані

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

Вихідні дані

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

Приклади