Problem description

Największą atrakcją wrocławskiego Rynku są zdecydowanie wrocławskie krasnale. Jednakże, prezydent miasta zauważył, że wiele dzieci ma duży problem z ich odnajdywaniem. Zastanawia się teraz jak to zmienić.

Po długich namysłach, prezydent postanowił, że niektóre krasnale będą zawierały tabliczkę, która będzie wskazywała na kolejnego krasnala. Każde dziecko, widząc taką tabliczkę, niezwłocznie pobiegnie do kolejnego, potem do kolejnego, i kolejnego… tak długo, aż w końcu dobiegnie do krasnala bez tabliczki, na którym zakończy zwiedzanie myśląc, że odwiedziło już wszystkie krasnale. Dlatego też prezydent musi zadbać, aby żadne dziecko nigdy nie biegało w nieskończoność, gdyż zakończyłoby się to interwencją rodziców i wielkim płaczem. Żadna tabliczka nie będzie też nigdy modyfikowana, gdyż spowodowałoby to za duże koszty dla miasta.

Teraz prezydent zastanawia się jaki efekt przynosi ciągłe dostawianie tabliczek przy krasnalach. Interesują go najbardziej weryfikacje czy dziecko, które przyszło zwiedzać Rynek jako i-te z kolei odwiedziło wybrane przez niego krasnale. Czy jesteś w stanie mu pomóc i odpowiedzieć na cały zestaw takich zapytań?

Wejście

W pierwszym wierszu wejścia podane są dwie liczby całkowite N, Q, oznaczające kolejno liczbę krasnali we Wrocławiu oraz liczbę wykonanych akcji.

W kolejnych Q wierszach znajdują się pojedyncze akcje. Każda z nich ma jeden z trzech formatów:

• 1 x y – oznacza to, że od teraz tabliczka przy krasnalu o numerze x będzie wskazywała na krasnala o numerze y,
• 2 x – oznacza, że dziecko o kolejnym numerze rozpoczęło zwiedzanie Rynku od krasnala numer x,
• 3 x i – oznacza zapytanie, czy dziecko, które przyszło zwiedzać Rynek jako i-te z kolei odwiedziło krasnala o numerze x.

Wyjście

Dla każdego zapytania typu ‘3 x i’ wypisz jeden wiersz zawierający słowo TAK jeśli dziecko o numerze i odwiedziło krasnala o numerze x, a w przeciwnym przypadku wypisz słowo NIE.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ Q ≤ 300 000, 1 ≤ x, y ≤ N, 1 ≤ i, wartość i nigdy nie będzie większa od liczby dzieci, które do tego momentu zwiedzały Rynek.

Ponadto, w każdej podgrupie w testach wartych dokładnie połowę punktów zachodzi warunek, że wszystkie zapytania dotyczące jednego dziecka występują bezpośrednio po jego przejściu przez daną ścieżkę.

Przykłady

4 9
1 4 3
2 4
3 3 1
1 2 3
2 2
3 1 2
1 3 1
2 2
3 1 3

TAK
NIE
TAK

6 12
1 2 1
1 3 2
1 4 2
1 5 4
1 6 1
2 5
3 2 1
3 5 1
3 6 1
2 6
3 1 2
3 5 2

TAK
TAK
NIE
TAK
NIE

4 12
1 2 1
1 4 3
2 2
3 1 1
3 3 1
2 4
3 3 2
3 4 2
1 3 2
2 4
3 2 3
3 4 3

TAK
NIE
TAK
TAK
TAK
TAK