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.
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.
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ą.
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.
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 8poprawnym rozwiązaniem jest:
TAK NIE TAK