Problem description

Back
Show PDF
Wrocławskie krasnale
(information-graph)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

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.

Podzadanie Warunki Punkty
1 N ≤ 1 000, Q ≤ 2 000 20
2 wszystkie tabliczki powstały zanim jakiekolwiek dziecko zaczęło zwiedzać Rynek 20
3 na każdego krasnala może wskazywać co najwyżej jedna tabliczka, dodatkowo dzieci rozpoczynały zwiedzanie od krasnali, na które w danym momencie nie wskazywała żadna tabliczka 20
4 brak dodatkowych ograniczeń 40

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

Wejście Wyjście Wyjaśnienie 
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

Pierwsze trzy akcje w tym przykładzie to:

  • obok krasnala o numerze 4 zostaje postawiona tabliczka wskazująca na krasnala o numerze 3,
  • dziecko o numerze 1 rozpoczyna zwiedzanie od krasnala 4, czyli odwiedza też krasnala o numezre 3,
  • pytamy czy dziecko o numerze 1 odwiedziło krasnala o numerze 3, odpowiedź to TAK.
Wejście Wyjście Wyjaśnienie 
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

Przykład spełnia warunki podzadania 2, oraz wszystkie zapytania dotyczące jednego dziecka występują bezpośrednio po jego zwiedzaniu.
Wejście Wyjście Wyjaśnienie 
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

Przykład spełnia warunki podzadania 3, oraz wszystkie zapytania dotyczące jednego dziecka występują bezpośrednio po jego zwiedzaniu.