Archiwum zadań programistycznych WWSI

Topologia sieci komputerowej to w większości przypadków ściśle strzeżona tajemnica każdego administratora. Ujawnienie tego typu informacji zwiększa ryzyko skutecznego ataku sieciowego, a tego chce uniknąć każdy dział IT! No może nie każdy ... każdy z wyjątkiem naszego. Jako, że jesteśmy beznadziejnymi administratorami sieci to jest nam całkowicie obojętne czy poznasz topologię naszego dzieła czy też nie. Tak właściwie to z chęcią Ci opiszemy budowę naszej sieci bo liczymy na to, że pomożesz nam rozwiązać problemy z łącznością między hostami jakie występują od początku jej działania.

W naszej sieci korzystamy ze sprzętu wyprodukowanego przez powszechnie szanowaną chińską firmę SHIT (Shanghai Internet Technologies). Routery tej firmy posiadają porty sieciowe, które potrafią realizować odbiór albo wysyłkę danych. Żaden port nie jest w stanie realizować obydwu tych funkcji. Jak zapewnili nas producenci tego typu jednofunkcyjne porty to technologia przyszłości ... wierzymy im! Dodatkowo nasze routery są wyposażone w bardzo zaawansowany protokół trasowania o nazwie BAD (Broadcast All Data), który w zasadzie nie korzysta z żadnych informacji o trasach tylko wysyła pakiety, które otrzyma przez wszystkie porty wychodzące. To niewątpliwa zaleta tego sprzętu, dzięki temu protokołowi nie musimy już konfigurować tras a przez nasze łącza przepływa trzy razy więcej danych(!), to chyba znak, że wcześniej coś było zatkane ;-)

Jak widzisz nie korzystamy z byle czego, potrzebujemy jednak twojej pomocy. Napisz program, który po wczytaniu opisu połączeń sieciowych będzie w stanie odpowiedzieć czy pakiet ping wysłany z jednego komputera w sieci dotrze do drugiego i z powrotem. Połączenia pomiędzy komputerami nie muszą być bezpośrednie. Oznacza to, że pakiet może zostać dostarczony za pośrednictwem innych hostów w sieci.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby naturalne n i m (1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 10⁴) określające odpowiednio ilość urządzeń w naszej sieci oraz ilość połączeń między nimi. W kolejnych m liniach znajdują się opisy połączeń. Każdy opis połączenia zawiera dwie liczby naturalne a i b (0 ≤ a, b < n). Oznaczają one, że z urządzenia o numerze a można przesłać dane do urządzenia o numerze b.

W kolejnej linii znajduje się liczba naturalna q (1 ≤ q ≤ 10⁵) określająca ilość zapytań. W następnych q liniach znajdują się zapytania. Każde zapytanie składa się z dwóch liczb s i d określających numer urządzenia źródłowego i numer urządzenia docelowego.

Wyjście

Dla każdego zapytania należy w osobnej linii wypisać TAK jeżeli istnieje trasa od komputera docelowego do źródłowego i z powrotem albo NIE w przeciwnym wypadku.

Przykład

Wejście:

4 4 
0 1 
1 3 
3 0 
0 2 
5 
0 1 
3 1 
2 0 
0 2 
1 2

Wyjście:

TAK 
TAK 
NIE 
NIE 
NIE