Bajtocki Bieg Uliczny

Limit pamięci: 64 MB

W centrum Bajtogrodu ma się jutro odbyć Bajtocki Bieg Uliczny. Ulice w Bajtogrodzie tworzą równomierną kratkę: wszystkie prowadzą z południa na północ bądź z zachodu na wschód. Uczestnikom biegu udostępniono jedynie pewne ich fragmenty.

Bajtazar ma się zająć rozstawieniem reklam sponsorów imprezy na niektórych skrzyżowaniach i w tym celu musi przyjrzeć się mapie trasy biegu. Mapa przedstawia fragmenty ulic, które udostępniono biegaczom. Zaznaczono na niej skrzyżowań oraz pionowych i poziomych odcinków ulic. Każdy odcinek zaczyna się i kończy na jakimś skrzyżowaniu i nie zawiera żadnych innych skrzyżowań. Odcinki ulic nie przecinają się poza skrzyżowaniami.

Skrzyżowania są ponumerowane od do . Bieg ma rozpocząć się na skrzyżowaniu numer i zakończyć na skrzyżowaniu numer . Biegacze mogą wybrać swoją trasę biegu, przy czym zobowiązani są biec tylko na południe lub na wschód i jedynie po odcinkach zaznaczonych na mapie. Odcinki ulic na mapie są dobrane tak, że biegnąc zgodnie z zasadami, z każdego miejsca da się dotrzeć do mety i każde miejsce jest osiągalne ze skrzyżowania startowego.

Bajtazar chciałby porozwieszać reklamy tak, żeby mieć pewność, że żaden biegacz nie zobaczy dwukrotnie reklamy tego samego sponsora. Wobec tego, dla niektórych par skrzyżowań Bajtazar musi sprawdzić, czy możliwe jest, by trasa jakiegoś uczestnika przebiegała przez obydwa skrzyżowania. Bieg startuje już jutro, dlatego pilnie potrzebny jest program, który pomoże mu w pracy.

Wejście

Pierwszy wiersz wejścia zawiera trzy liczby całkowite , i (, , ). Oznaczają one odpowiednio liczbę skrzyżowań na trasie biegu, liczbę odcinków na mapie oraz liczbę par skrzyżowań do sprawdzenia.

Kolejne wierszy opisuje położenia skrzyżowań. W -tym spośród nich znajdują się współrzędne -tego skrzyżowania w postaci dwóch liczb całkowitych , (). Dodatkowo, i . W danym miejscu może znajdować się co najwyżej jedno skrzyżowanie. Osie układu współrzędnych utożsamiamy w naturalny sposób z kierunkami świata: oś OX prowadzi na wschód, zaś oś OY - na północ.

Każdy z kolejnych wierszy zawiera opis jednego odcinka na mapie składający się z pary liczb całkowitych , () oznaczających numery skrzyżowań połączonych tym odcinkiem. Wszystkie te odcinki są pionowe lub poziome i nie mają punktów wspólnych poza wspólnymi końcami na skrzyżowaniach.

W następnych wierszach znajdują się opisy par skrzyżowań do sprawdzenia. W -tym z tych wierszy znajdują się dwie liczby całkowite , (, ).

Wyjście

Twój program powinien wypisać wierszy. W -tym spośród tych wierszy powinno znaleźć się słowo TAK, jeśli trasa pewnego uczestnika biegu może prowadzić przez skrzyżowania i (w dowolnej kolejności). W przeciwnym wypadku należy wypisać NIE.

Przykład

Dla danych wejściowych:

9 10 4
1 6
2 6
4 4
1 4
3 4
4 6
6 4
3 1
6 1
1 2
4 1
2 6
3 6
5 4
5 3
5 8
3 7
7 9
9 8
4 8
2 5
8 7
7 6

poprawną odpowiedzią jest:

TAK
NIE
NIE
TAK

Autor zadania: Jakub Łącki.