Problem description

Janek ostatnio zainteresował się teorią grafów. Szczególnie spodobały mu się cykle — a najbardziej te najkrótsze. Dziś analizuje graf nieskierowany, prosty, składający się z n wierzchołków ponumerowanych od 1 do n i m krawędzi.

Janek chciałby sprawdzić, czy w jego grafie istnieje trójkąt zawierający wierzchołek 1, czyli taki ciąg trzech różnych wierzchołków, z których każdy jest połączony z następnym, a ostatni dodatkowo połączony z pierwszym, i który zawiera wierzchołek numer 1.

Janek uważa, że sprawdzanie tego ręcznie byłoby zbyt czasochłonne, więc poprosił cię o pomoc. Twoim zadaniem jest stwierdzić, czy istnieje taki cykl.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite n i m — liczba wierzchołków i liczba krawędzi w grafie. W kolejnych m liniach znajdują się po dwie liczby u i v oznaczające, że w grafie istnieje krawędź między wierzchołkami u i v.

Wyjście

Wypisz TAK, jeśli istnieje cykl długości 3 zawierający wierzchołek 1, w przeciwnym razie wypisz NIE.

Uwaga: słowa TAK i NIE muszą być zapisane wielkimi literami.

Ograniczenia

• 1 ≤ n, m ≤ 3 ⋅ 10⁵
• 1 ≤ u, v ≤ n
• Graf jest prostym grafem nieskierowanym (nie zawiera pętli ani wielokrotnych krawędzi).

Przykład

4 5
1 2
3 2
1 4
1 3
4 2

TAK

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

NIE