W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Gonitwa jest grą planszową dla dwóch osób i . Plansza do gry składa się z pól ponumerowanych kolejnymi liczbami naturalnymi, poczynając od . 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 zawsze wykonuje swój ruch przed ruchem gracza .
Powiemy, że gracz dogonił gracza , jeżeli oba piony znajdą się na tym samym polu. Rozstrzygnij, czy dla danych początkowych położeń obu pionów, gracz może dogonić gracza , niezależnie od tego jak dobrze gra gracz . Jeśli tak, to po ilu rundach gracz dogoni gracza , jeżeli gracz stara się uciekać jak najdłużej, a gracz stara się dogonić gracza jak najszybciej i obaj grają optymalnie?
Rozważmy planszę przedstawioną na rysunku. Sąsiednie pola planszy są połączone odcinkami. Jeżeli na początku gry pion gracza znajduje się na polu , natomiast pion gracza jest na polu , to gracz dogoni w trzeciej rundzie, o ile obaj gracze grają optymalnie. Gdyby pion gracza znajdował się początkowo na polu , to ruszając z pola gracz nie ma szans na dogonienie , jeżeli tylko ten gra optymalnie.
Napisz program, który:
W pierwszym wierszu standardowego wejścia znajdują się cztery liczby całkowite oraz , oddzielone pojedynczym odstępem, gdzie: , , oraz . 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 oraz numer pola, na którym jest umieszczony pion gracza .
W każdym z następnych wierszy 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ć w pierwszym i jedynym wierszu standardowego wyjścia jedno słowo NIE, jeśli gracz nigdy nie dogoni gracza , a w przeciwnym przypadku jedną liczbę całkowitą — liczbę rund, po których, gracz dogoni gracza .
Dla danych wejściowych:
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
poprawną odpowiedzią jest:
3
Autor zadania: Adam Borowski.