Gra w karty

Bajtek i Bitek są światowej klasy mistrzami w grze karcianej Magiczne Stwory. Dzisiaj wieczorem odbędzie się epicki pojedynek, który rozstrzygnie, któremu z nich będzie przysługiwał dożywotni tytuł Arcymistrza.

Zasady gry w Magiczne Stwory są dość osobliwe. Każdy z graczy posiada n różnych talii. Właściwa rozgrywka poprzedzona jest fazą wybierania talii. Począwszy od Bajtka, gracze będą na przemian odrzucali po jednej talii przeciwnika. Gdy każdemu z nich zostanie tylko jedna talia, rozpocznie się znacznie bardziej ekscytująca, druga i ostatnia faza gry. Co ciekawe, przebieg drugiej fazy nie zależy od strategii graczy, ani nawet od przypadku – dla każdej potencjalnej pary talii dopuszczonych do ostatecznej rozgrywki, z góry wiadomo, jak ona się zakończy – wygraną Bajtka, wygraną Bitka bądź remisem.

Twoim zadaniem jest stwierdzić, czy Bajtek posiada strategię wygrywającą. Powiemy, że Bajtek ma strategię wygrywającą, jeśli wygra on ostateczną rozgrywkę, gdy obaj gracze odrzucają talie przeciwnika w sposób optymalny. Jeżeli Bajtek nie posiada strategii wygrywającej, należy stwierdzić, czy posiada on przynajmniej strategię remisującą, a więc, czy może on spowodować, że jego rywal nie otrzyma zaszczytnego tytułu Arcymistrza, jeśli obaj gracze postępują optymalnie.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita t (1 ≤ t ≤ 20), oznaczająca liczbę przypadków testowych.

Opis każdego przypadku testowego rozpoczyna się wierszem zawierającym dwie liczby całkowite n i m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000), oznaczające odpowiednio liczbę talii każdego z graczy oraz liczbę par talii, których wybór do drugiej fazy nie powoduje remisu. Talie każdego z graczy są ponumerowane liczbami od 1 do n. Dalej następuje m wierszy postaci a w b, (1 ≤ a, b ≤ n, w ∈ {<, >}). Jeżeli w = <, to taki wiersz oznacza, że talia Bajtka o numerze a przegrywa z talią Bitka o numerze b. Jeśli zaś w = >, to talia Bajtka o numerze a wygrywa z talią Bitka o numerze b. Dla danej uporządkowanej pary (a, b) numerów talii (odpowiednio Bajtka i Bitka), wiersz postaci a w b pojawia się w opisie danego przypadku testowego co najwyżej raz; jeśli taki wiersz nie pojawia się wcale, to znaczy, że ostateczna rozgrywka po wyborze talii Bajtka o numerze a oraz talii Bitka o numerze b kończy się remisem.

Na wyjście należy wypisać t wierszy, po jednym dla każdego przypadku testowego, w kolejności występowania przypadków na wejściu.

Dla danego przypadku należy wypisać WYGRANA, jeżeli Bajtek ma strategię wygrywającą; REMIS, jeżeli nie ma on strategii wygrywającej, ale posiada strategię remisującą oraz PRZEGRANA w pozostałych przypadkach.