题目描述

$N$ 个小朋友（编号为 $0,1,2,\dots,N-1$）一起玩石头剪子布游戏。

其中一人为裁判，其余的人被分为三个组（有可能有一些组是空的），第一个组的小朋友只能出石头，第二个组的小朋友只能出剪子，第三个组的小朋友只能出布，而裁判可以使用任意手势。

你不知道谁是裁判，也不知道小朋友们是怎么分组的。

然后，孩子们开始玩游戏，游戏一共进行 $M$ 轮，每轮从 $N$ 个小朋友中选出两个小朋友进行猜拳。

你将被告知两个小朋友猜拳的胜负结果，但是你不会被告知两个小朋友具体使用了哪种手势。

比赛结束后，你能根据这些结果推断出裁判是谁吗？如果可以的话，你最早在第几轮可以找到裁判。

输入格式

输入可能包含多组测试用例。

每组测试用例第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $a, b$，中间夹着一个符号 $(>, =, <)$，表示一轮猜拳的结果。

两个整数为小朋友的编号，$a > b$ 表示 $a$ 赢了 $b$，$a = b$ 表示 $a$ 和 $b$ 平手，$a < b$ 表示 $a$ 输给了 $b$。

输出格式

每组测试用例输出一行结果：

• 如果可以找到裁判，且只有一个人可能是裁判，则输出 Player x can be determined to be the judge after y lines，其中 $x$ 是裁判编号，$y$ 是确定轮数。
• 如果可以找到裁判，但裁判的可能人选多于 1 个，则输出 Can not determine。
• 如果根据输入推断的结果是必须没有裁判或者必须有多个裁判，则输出 Impossible。

具体格式可参考样例。

样例

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

Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines

样例解释

测试用例 1

3 3
0<1
1<2
2<0

• 共 3 个小朋友，3 轮比赛。
• 结果：0<1（0 输给 1），1<2（1 输给 2），2<0（2 输给 0）。
• 分析：如果不存在裁判，那么三个小朋友应该分别属于石头、剪刀、布三个组，这样胜负关系会形成循环。但这里的胜负关系形成了一个矛盾循环：0 输给 1，1 输给 2，2 输给 0，这是不可能的（因为石头剪刀布不可能出现 A 输给 B，B 输给 C，C 输给 A 的循环，除非有人是裁判）。
• 但仅凭这 3 轮无法唯一确定裁判是谁（可能是 0、1、2 中的任意一个）。
• 输出 Can not determine。

测试用例 2

3 5
0<1
0>1
1<2
1>2
0<2

• 共 3 个小朋友，5 轮比赛。
• 前 4 轮：0 和 1 之间一胜一负，1 和 2 之间一胜一负。这说明 0、1、2 中至少有两人是裁判（因为非裁判的小朋友只能出固定手势，不可能对同一个人既胜又负）。
• 实际上，如果 1 是裁判，那么 0 和 2 可以分别属于不同组（比如 0 出石头，2 出布），这样 0<2 成立。检查所有约束，只有 1 是裁判时才不矛盾。
• 在第 4 轮结束后可以唯一确定裁判是 1。
• 输出 Player 1 can be determined to be the judge after 4 lines。

测试用例 3

4 4
0<1
0>1
1<2
1>2
2<3
2>3

实际上输入为：

4 4
0<1
0>1
2<3
2>3

• 共 4 个小朋友，4 轮比赛。
• 0 和 1 之间一胜一负，2 和 3 之间一胜一负。
• 这意味着 0 和 1 中至少有一人是裁判，2 和 3 中至少有一人是裁判。
• 但裁判只能有一个人，所以这是不可能的（因为必须有两个裁判才能满足条件）。
• 输出 Impossible。

测试用例 4

1 0

• 只有一个小朋友，没有比赛。
• 那么这个人就是裁判（因为没有其他可能性）。
• 在第 0 轮就可以确定。
• 输出 Player 0 can be determined to be the judge after 0 lines。

数据范围

• $1 \le N \le 500$
• $0 \le M \le 2000$

算法思路

此题可以用扩展域并查集或带权并查集来建模。

将每个小朋友 $i$ 拆成三个域：

• $i_A$ 表示 $i$ 属于石头组
• $i_B$ 表示 $i$ 属于剪刀组
• $i_C$ 表示 $i$ 属于布组

根据游戏规则：

• 石头赢剪刀，剪刀赢布，布赢石头。
• 平手表示两人属于同一组。

对于一轮结果：

• $a = b$：表示 $a$ 和 $b$ 属于同一组。
• $a > b$：表示 $a$ 赢 $b$，即如果 $a$ 出石头则 $b$ 出剪刀，等等。
• $a < b$：表示 $a$ 输 $b$，即如果 $a$ 出石头则 $b$ 出布，等等。

裁判可以任意出手，所以包含裁判的约束总是成立。

判断方法： 枚举每个小朋友作为裁判，检查去掉该小朋友的所有约束后，剩余约束是否矛盾（用并查集判断）。如果不矛盾，则该小朋友可能是裁判。

确定最早轮数： 对于每个可能是裁判的小朋友，找到最早出现矛盾的轮数（如果将他作为裁判，该轮之前的约束都成立，该轮出现矛盾）。所有可能裁判的最早矛盾轮数的最大值，就是确定裁判的最早轮数。

输出规则总结

1. 如果可能裁判人数 = 0：输出 Impossible。
2. 如果可能裁判人数 > 1：输出 Can not determine。
3. 如果可能裁判人数 = 1：输出 Player x can be determined to be the judge after y lines。