E - Gonitwa

Autor: Adam Borowski (zadanie z V Olimpiady Informatycznej)

Gonitwa jest grą planszową dla dwóch osób A i B. Plansza do gry składa się z pól ponumerowanych kolejnymi liczbami naturalnymi, poczynając od 1. Dla każdej pary różnych pól wiadomo, czy są sąsiednie, czy nie. Każdy z graczy dysponuje jednym pionem, który początkowo znajduje się na wskazanym z góry polu planszy, każdy pion na innym polu. Ruch gracza polega na przesunięciu własnego piona na jedno z sąsiednich pól lub pozostawieniu piona na miejscu.

Plansza ma następujące właściwości:

Gra składa się z wielu rund następujących po sobie. W jednej rundzie każdy z graczy wykonuje jeden ruch, przy czym gracz A zawsze wykonuje swój ruch przed ruchem gracza B. Powiemy, że gracz B dogonił gracza A, jeżeli oba piony znajdą się na tym samym polu.

Zadanie

Napisz program, który stwierdzi czy dla danej planszy gracz B może dogonić gracza A przy założeniu, że obaj gracze grają optymalnie.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita d. Po niej następują opisy d plansz.
W pierwszym wierszu opisu planszy znajdują się cztery liczby całkowite N, M, A oraz B, oddzielone pojedynczym odstępem, gdzie: 2<=N<=3000, n-1<=M<=15000, 1<=A,B<=n oraz A<>B. Są to odpowiednio: liczba pól na planszy, liczba wszystkich różnych par (nieuporządkowanych) tych pól, które ze sobą sąsiadują, numer pola, na którym jest umieszczony pion gracza A oraz numer pola, na którym jest umieszczony pion gracza B. W każdym z następnych M wierszy zestawu znajdują się dwie różne liczby całkowite dodatnie oddzielone pojedynczym odstępem. Liczby w każdym z tych wierszy są numerami dwóch pól, które ze sobą sąsiadują.

Wyjście

Twój program powinien zapisać na wyjściu dla każdej planszy (w osobnej linii) słowo TAK lub NIE, mówiące czy gracz B jest w stanie dogonić gracza A.

Przykład

Dla wejścia:

3
2 1 1 2
1 2
5 5 5 3
1 2
2 3
3 4
4 1
1 5
9 11 9 4
1 2
3 2
1 4
4 7
7 5
5 1
6 9
8 5
9 8
5 3
4 8
poprawnym rozwiązaniem jest:
TAK
NIE
TAK