카드 게임

바이텍과 비텍은 세계 최고 수준의 카드 게임 Magiczne Stwory (Magic Creatures) 선수다. 오늘 저녁 두 사람이 맞붙는 대결에서 누가 평생 칭호인 그랜드마스터를 얻을지 정해진다. 규칙은 꽤 특이하다. 각 플레이어는 서로 다른 덱을 n개씩 가진다. 본격적인 대전 전에 덱을 고르는 단계가 있다. 바이텍부터 시작해서 두 플레이어가 번갈아 상대의 덱을 하나씩 버린다. 각자 덱이 하나씩만 남으면 두 번째이자 마지막 단계인 실제 대전이 시작된다. 이 단계의 결과는 전략이나 운과 무관하다. 최종 대전에 올라갈 수 있는 덱 쌍마다 바이텍의 승리, 비텍의 승리, 무승부 중 결과가 이미 정해져 있다. 과제는 바이텍에게 필승 전략이 있는지 판단하는 것이다. 두 플레이어가 상대 덱을 최적으로 버렸을 때 바이텍이 최종 대전에서 이기면 바이텍은 필승 전략을 가진다. 필승 전략이 없다면 바이텍에게 적어도 무승부 전략이 있는지 확인한다. 즉 두 플레이어가 최적으로 행동할 때 상대가 그랜드마스터 칭호를 얻지 못하게 할 수 있는지 본다.

첫 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 20)가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 n과 m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000)이 주어진다. n은 각 플레이어가 가진 덱의 수이고, m은 두 번째 단계에서 무승부가 나지 않는 덱 쌍의 수이다. 각 플레이어의 덱은 1부터 n까지 번호가 붙어 있다. 이어서 m개의 줄이 a w b 형태로 주어진다 (1 ≤ a, b ≤ n, w ∈ {<, >}). w가 <이면 바이텍의 덱 a가 비텍의 덱 b에게 진다는 뜻이다. w가 >이면 바이텍의 덱 a가 비텍의 덱 b를 이긴다는 뜻이다. 순서쌍 (a, b)에 대한 줄은 한 테스트 케이스에 최대 한 번 나온다. 어떤 줄에도 나오지 않는 쌍은 두 덱으로 최종 대전을 치르면 무승부가 된다는 뜻이다.

각 테스트 케이스마다 입력 순서대로 한 줄씩 출력한다. 바이텍에게 필승 전략이 있으면 WYGRANA, 필승 전략은 없지만 무승부 전략이 있으면 REMIS, 나머지 경우에는 PRZEGRANA를 출력한다.