FRAKTAL - konkurs programistyczny

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, b ≤ n; a ≠ b) 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