题目描述

题目译自 PA 2016 Runda 1 Gra w karty

Bajtek 和 Bitek 是卡牌游戏《魔法生物》的世界级大师。今晚将举行一场史诗般的对决，决定谁将获得终身的“大宗师”称号。

《魔法生物》的规则颇为独特。每个玩家拥有 $n$ 套不同的卡牌。正式比赛前有一个选择卡牌阶段。从 Bajtek 开始，玩家将轮流丢弃对方的一套卡牌。直到双方各剩下一套卡牌时，将进入更为激动人心的第二阶段，也是最后一个阶段。有趣的是，第二阶段的进程不受玩家策略甚至运气的影响——对于每一对可能进入最终对决的卡牌组合，结果是预先确定的：Bajtek 获胜、Bitek 获胜或平局。

你的任务是判断 Bajtek 是否拥有获胜策略。我们说 Bajtek 拥有获胜策略，如果在双方玩家以最优方式丢弃对方卡牌的情况下，他能赢得最终对决。如果 Bajtek 没有获胜策略，则需要判断他是否至少拥有平局策略，即是否能在双方均以最优方式行动的情况下，使对手无法获得「大宗师」称号。

输入格式

输入数据的第一行包含一个整数 $t$ $(1 \leq t \leq 20)$，表示测试用例数量。

每个测试用例的描述从一行开始，包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 100000, 0 \leq m \leq 200000)$ 分别表示每个玩家的卡牌套数和不导致平局的卡牌对数量。每个玩家的卡牌编号为从 $1$ 到 $n$ 的整数。

接下来有 $m$ 行，每行格式为 $a$ $w$ $b$（$1 \leq a, b \leq n$，$w \in \{\texttt{<}, \texttt{>}\}$）。如果 $w = \texttt{<}$，表示 Bajtek 的卡牌 $a$ 输给 Bitek 的卡牌 $b$；如果 $w = \texttt{>}$，表示 Bajtek 的卡牌 $a$ 赢过 Bitek 的卡牌 $b$。对于给定的有序对 $(a, b)$（分别对应 Bajtek 和 Bitek 的卡牌编号），格式为 $a$ $w$ $b$ 的行在该测试用例描述中最多出现一次；如果这样的行未出现，则表示选择 Bajtek 的卡牌 $a$ 和 Bitek 的卡牌 $b$ 进行最终对决将以平局结束。

输出格式

输出应包含 $t$ 行，每行对应一个测试用例，按输入顺序排列。

对于每个测试用例，输出 WYGRANA，如果 Bajtek 拥有获胜策略；输出 REMIS，如果他没有获胜策略但拥有平局策略；其他情况下输出 PRZEGRANA。

3
5 5
5 > 5
1 > 5
3 > 5
4 > 5
2 > 5
2 2
1 > 1
1 > 2
1 1
1 < 1

WYGRANA
REMIS
PRZEGRANA