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:

• nie zawiera trójkątów, tzn. nie istnieją trzy różne pola, takie że każde dwa z nich są sąsiednie,
• każde pole może być osiągnięte zarówno przez gracza A, jak i przez gracza B.

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. Rozstrzygnij, czy dla danych początkowych położeń obu pionów, gracz B może dogonić gracza A, niezależnie od tego jak dobrze gra gracz A. Jeśli tak, to po ilu rundach gracz B dogoni gracza A, jeżeli gracz A stara się uciekać jak najdłużej, a gracz B stara się dogonić gracza A 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 A znajduje się na polu 9, natomiast pion gracza B jest na polu 4, to gracz B dogoni A w trzeciej rundzie, o ile obaj gracze grają optymalnie. Gdyby pion gracza A znajdował się początkowo na polu 8, to ruszając z pola 4 gracz B nie ma szans na dogonienie A, jeżeli tylko ten gra optymalnie.

Zadanie

Napisz program, który:

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

3