Двухцветность

В 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$ и не обрабатывается.

Выходные данные

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

Примеры