Wybór

Limit pamięci: 64 MB

Podejmowanie decyzji nigdy nie było mocną stroną Bajtazara. Za każdym razem, gdy porusza się po Bajtogrodzie i wie, że do celu może dotrzeć co najmniej dwiema kompletnie różnymi trasami, długo głowi się nad tym, którędy pojechać. Z tego powodu Bajtazar bardzo ucieszył się na wiadomość o planowanych remontach - pojawiła się szansa, że zamknięcie niektórych ulic nieco ułatwi mu życie.

W Bajtogrodzie jest skrzyżowań połączonych dwukierunkowymi ulicami. Dwie trasy między parą skrzyżowań nazywamy kompletnie różnymi, jeśli nie istnieje ulica wchodząca w skład obydwóch tras. Mogą jednak istnieć skrzyżowania, przez które prowadzą obydwie trasy.

Bajtazar śledzi dokładnie informacje o zamknięciach ulic. Z początku potrafił bez trudu orientować się, czy gdy jedzie dokądś, ma do wyboru co najmniej dwie kompletnie różne trasy, jednak z czasem aktualizowanie tych informacji stało się trudne. Poprosił Cię więc o napisanie programu, który zrobi to za niego.

Wejście

W pierwszym wierszu znajdują się trzy liczby całkowite , oraz (, ) oznaczające kolejno liczbę skrzyżowań w Bajtogrodzie, liczbę łączących je ulic oraz liczbę zdarzeń, które miały miejsce. Skrzyżowania są ponumerowane od do .

Kolejne wierszy zawiera opisy ulic, każdy w postaci dwóch liczb całkowitych , (, ). Taka para oznacza, że skrzyżowania oraz są połączone dwukierunkową ulicą. Każda para skrzyżowań może być połączona co najwyżej jedną ulicą.

W kolejnych wierszach znajdują się opisy kolejno następujących zdarzeń w postaci znaku oraz dwóch liczb całkowitych , (, , ). Zdarzenia są podane w kolejności chronologicznej. Wartość oznacza, że ulica między skrzyżowaniami do została zamknięta. Zamykana ulica zawsze istnieje i nie była wcześniej zamknięta. Remonty mogą być prowadzone chaotycznie i w szczególności może się zdarzyć, że doprowadzą do zamknięcia wszystkich ulic w mieście. Z kolei wartość oznacza, że Bajtazar chce dostać się ze skrzyżowania do i chciałby wiedzieć, czy może to zrobić na co najmniej dwa kompletnie różne sposoby, biorąc pod uwagę jedynie te ulice, które nie zostały wcześniej zamknięte.

Wyjście

Wypisz po jednym wierszu dla każdego zdarzenia typu P, w kolejności zgodnej z wejściem. Jeśli istnieją dwie trasy łączące podaną parę skrzyżowań i przebiegające po rozłącznych zbiorach ulic, w odpowiednim wierszu wypisz TAK. W przeciwnym przypadku, należy wypisać NIE. Możesz założyć, że wyjście nie będzie puste.

Przykład

Dla danych wejściowych:

7 8 7
1 2
1 3
1 4
2 3
3 4
3 7
7 4
5 6
Z 1 4
P 1 3
P 2 4
Z 1 3
P 1 3
Z 6 5
P 5 6

poprawną odpowiedzią jest:

TAK
TAK
NIE
NIE

Autor zadania: Jakub Łącki.