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

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

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

Вхідні дані

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

Вихідні дані

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