İkirənglilik

1976-cı ildə "Dörd rəng teoremi" kompüter vasitəsilə sübut edilmişdir. Bu teorem təsadüfi xəritənin yalnız dörd rəngdən istifadə etməklə rənglənə biləcəyini iddia edir ki, heç bir sahə qonşu sahələrlə eyni rəngdə olmasın.

Sizə oxşar, lakin daha sadə bir məsələni həll etmək təklif olunur. Təsadüfi verilmiş əlaqəli qrafın iki rəngli olub-olmadığını müəyyən etmək lazımdır. Yəni, onun zirvələrinə elə rənglər (cəmi iki rəng var) təyin etmək mümkündürmü ki, heç bir iki qonşu zirvə eyni rəngdə olmasın. Məsələni sadələşdirmək üçün aşağıdakıları qəbul etmək olar:

• qrafda döngələr yoxdur.

• qraf istiqamətsizdir. Yəni, əgər zirvə $a$ zirvə $b$ ilə bağlıdırsa, onda $b$ də $a$ ilə bağlıdır.

• qraf əlaqəlidir. Yəni, təsadüfi bir zirvədən digərinə həmişə ən azı bir yol mövcuddur.

Giriş verilənləri

Bir neçə testdən ibarətdir. Hər bir test zirvələrin sayını göstərən bir sətirlə başlayır $n(0\le n\le 1000)$. İkinci sətir kənarların sayını göstərir $l(1\le l\le 250000)$. Bundan sonra $l$ sətir gəlir, hər biri iki zirvə arasında əlaqəni göstərən iki ədəd ehtiva edir. Qrafdakı zirvələr $a(1\le a\le n)$ ədədi ilə işarələnəcək. Sonuncu test $n=0$ ehtiva edir və işlənmir.

Çıxış verilənləri

Daxil olan qrafın iki rəngli olub-olmadığını müəyyən edin və nümunədə göstərildiyi kimi müvafiq mesajı çıxarın.

Nümunələr