Wirus

Limit pamięci: 128MB

Nasze komputery zaatakował wirus! Nie potrafimy się go pozbyć, ale odkryliśmy zasadę jego działania. Otóż wirus przyjmuje listę par liczb całkowitych (A, B), po czym dla każdej pary wykonuje taką operację:

Jedyne co potrafimy zrobić, to odwrócić niektóre pary w pamięci wirusa, to znaczy jeśli mamy parę (A, B), to możemy ją zamienić na (B, A).

Twoim zadaniem jest wyznaczyć, czy możliwe jest zneutralizowanie wirusa tą metodą, to znaczy aby po tych operacjach początkowa wartość żadnej komórki pamięci nie uległa zmianie. W przypadku gdy jest to możliwe, wypisz dla każdej pary, czy należy ją odwrócić.

Największy adres atakowanej komórki nie będzie przekraczał 500000.

Wejście

W pierwszym wieszu znajduje się liczba całkowita k (k<=106) oznaczająca liczbę operacji wykonywanych przez wirusa. W następnych k wierszach znajdują się po dwie liczby A i B (A!=B) oznaczające parę (A, B). Pary mogą się powtarzać.

Wyjście

Gdy możliwa jest neutralizacja w pierszej linii wypisz "TAK", a następnie dla każdej operacji wypisz zgodnie z kolejnością pojawiania się ich na wejściu, czy należy odwrócić parę. Jeśli odwrócić wypisz literę O, jeśli zostawić Z. Gdy nie da się unieszkodliwić wirusa wypisz tylko "NIE". Wypisz dowolne poprawne rozwiązanie.

Przykład

Wejście:
3
1 2
3 2
3 1

Przykladowe wyjscie:
TAK
Z
O
Z

Wejście:
3
1 2
2 3
3 2

Wyjście:
NIE