Problem description

Zadanie jest proste: rozstrzygnąć, czy możemy pokolorować wierzchołki danego grafu dwoma kolorami w ten sposób, żeby żadne dwa sąsiadujące wierzchołki nie miały tego samego koloru.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne N oraz M oznaczające kolejno liczbę wierzchołków oraz liczbę krawędzi grafu. W następnych M wierszach następują opisy krawędzi. Każdy opis składa się z dwóch liczb u oraz v oznaczających, że w grafie jest krawędź między wierzchołkami u i v.

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać słowo TAK, jeżeli graf można pokolorować wg warunków zadania, a w przeciwnym wypadku należy wypisać NIE.

Ograniczenia

1 ≤ N, M ≤ 1 000 000, 1 ≤ u, v ≤ N.

Przykład

4 3
1 2
2 3
3 4

TAK

7 7
1 2
2 3
3 1
4 5
5 6
6 7
7 4

NIE