Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_AA_10 - Rysunek Mikołaja

Mały Mikołaj na swoje pierwsze urodziny dostał rysunek do pokolorowania.

Kolorowanka to mapa łąki, na której mieszkają zające bielaki oraz szaraki. Na mapie przedstawiona jest sieć podziemnych tuneli, na końcu których mieszczą się zajęcze nory. Sieć tuneli jest tak skonstruowana, że zawsze istnieje przejście, niekoniecznie bezpośrednie, pomiędzy dwoma dowolnymi norami.

Mikołaj chce pokolorować zajęcze nory w ten sposób, aby na końcach każdego tunelu, z jednej strony norę miały zające bielaki, a z drugiej strony zające szaraki. Nasz bohater zastanawia się, czy w ogóle jest to wykonalne?

Wejście

W pierwszym wierszu znajdują się dwie liczby naturalne n (2 ≤ n ≤ 1000000) oraz m (1 ≤ m ≤ 2000000) określające liczbę nor na mapie oraz liczbę tuneli między nimi.

W kolejnych m wierszach znajdują się po dwie liczby naturalne a oraz b (1 ≤ a, bn; ab) określające numery nor pomiędzy, którymi istnieje tunel.

Wyjście

Na wyjściu należy wypisać słowo TAK, jeśli Mikołaj będzie mógł pokolorować rysunek zgodnie ze swoimi założeniami albo słowo NIE w przeciwnym wypadku.

Przykład 1

Wejście:

5 4
1 3
2 3
2 4
2 5

Wyjście:

TAK

Wyjaśnienie do przykładu:

Jednym z możliwych rozwiązań jest pokolorowanie nor 1 i 2 jako nor zajęcy bielaków, zaś nor 3, 4 i 5 jako nor zajęcy szaraków.

Przykład 2

Wejście:

6 10
1 2
2 3
3 4
4 5
5 6
6 1
1 4
1 5
2 4
2 6

Wyjście:

NIE

Dodane przez:Marcin Kasprowicz
Data dodania:2021-04-14
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.