POLSKI SPOJ

Rozważamy grę logiczną rozgrywaną przez dwóch graczy na planszy będącej grafem skierowanym, a więc złożonej ze skończonego zbioru pól ze strzałkami poprowadzonymi pomiędzy niektórymi polami. Zakładamy, że nie ma strzałek-pętli o tym samym polu początkowym i końcowym, ani strzałek równoległych (tj. więcej niż jednej strzałki o wspólnym: początku i końcu), dopuszczalne jest natomiast wystąpienie dwóch strzałek biegnących w przeciwnych kierunkach. Na niektórych polach rozmieszczone są białe pionki, przy czym na żadnym z pól nie stoi ich więcej niż jeden. Ruchy wykonuje się naprzemiennie (gracz nie może zrzec się ruchu, gdy przypadnie jego kolejka). Posunięcie polega na wyborze jednego z pionków i przemieszczeniu go wzdłuż którejś ze strzałek wychodzących z pola, na którym spoczywał, na pole końcowe tejże strzałki. Jeżeli pion po wykonaniu ruchu znajdzie się na polu zajętym przez inny pionek, oba pionki zostają zbite i usunięte z planszy. Przegrywa pierwszy z graczy, który podczas swojej kolejki nie może wykonać ruchu. Jest to możliwe w sytuacjach, gdy wszystkie pionki zostały już zbite, lub gdy pozostające na planszy pionki okupują pola, z których nie wychodzą żadne strzałki.

Cel zadania

Należy napisać program pozwalający na ocenę bieżącej sytuacji w grze dla zadanych: planszy i rozmieszczenia nań pionów. Każdą pozycję należy przyporządkować do jednego z trzech typów (takie przyporządkowanie jest możliwe dla każdej nielosowej, skończenie-stanowej gry o sumie zerowej dwóch graczy z pełną informacją):

• wygrywająca – gracz, który ma właśnie wykonać ruch, poprzez odpowiednie poprowadzenie rozgrywki jest w stanie doprowadzić do swojego zwycięstwa, bez względu na sposób obrony przeciwnika,
• przegrywająca – jakkolwiek nie prowadziłby rozgrywki gracz mający wykonać posunięcie, jego przeciwnik będzie w stanie zmusić go do przegranej.
• remisowa – obaj gracze stosując odpowiednie strategie mogą w nieskończoność unikać własnej klęski (ta definicja nie wyklucza zwycięstwa gracza startującego z pozycji remisowej – w przypadku gdy jego oponent grając popełni błąd).

Przykład 1. Poniższa sytuacja na 5-polowej planszy z dwoma pionami (na polach o numerach 0 i 3) jest przegrywająca, gdyż jakikolwiek ruch nie wykonałby pierwszy gracz, drugi znajdzie się w pozycji wygrywającej.

Ruch pionem z pola 0 doprowadza do sytuacji, w której drugi gracz wygrywa w jednym posunięciu bijąc oba piony na polu 3. Natomiast po ruchu z pola 3 drugi gracz może odpowiedzieć przemieszczając pionek z 0 na 1, następnie pierwszy gracz może już tylko przesunąć pionek na 3 i drugi gracz znów wygrywa.

Przykład 2. Poniższa sytuacja z 4 pionami na 5-polowej planszy jest remisowa.

Chociaż ten z graczy, który pierwszy dokona ruchu bijącego stawia siebie w pozycji przegranej, obaj przeciwnicy mogą dowolnie długo unikać wykonania bicia „goniąc się” w trójkącie utworzonym z pól 1, 3 i 4.

Wejście

W pierwszej linii podana jest liczba n pól planszy (n > 1). W kolejnych n liniach znajdują oddzielone spacjami: numer kolejnego pola (od 0 do n-1), liczba wychodzących zeń strzałek oraz numery pól końcowych tychże strzałek.

Kolejna linia (po wierszu opisującym strzałki wychodzące z pola numer n-1) zawiera liczbę l rozmieszczeń pionków na zadanej wcześniej planszy, których status należy określić (1 <= l <= 250).

Każda z dalszych l linii zawiera jedno ustawienie pionków na planszy. Są to kolejno oddzielone spacjami liczby: ilość p rozstawionych pionków (1 <= p <= n) oraz numery zajmowanych przez nie pól.

Przyjęte ograniczenia rozmiaru danych:
dla małych testów (ok. 75% punktów możliwych do zdobycia): n <= 15, p <= 6,
dla wszystkich testów: n + p <= 36.

Wyjście

W kolejnych wierszach program wypisuje po jednej literze określającej status sytuacji z kolejnych l ustawień pionków na planszy. Oznaczenia: W – pozycja wygrywająca, P – pozycja przegrywająca, R – pozycja remisowa.

Przykład

Podany poniżej zestaw testowy dotyczy sytuacji z przykładu 1, a także dwóch innych pozycji (kształt planszy bez zmian): z tylko jednym pionem ustawionym na polu 2 oraz z trzema pionami w górnych polach.

Wejście:
5
0 2 1 2
1 1 3
2 1 3
3 1 4
4 0
3
2 0 3
1 2
3 0 1 2

Wyjście:
P
P
W