题目描述

$N$ children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?

输入格式

Input contains multiple test cases. Each test case starts with two integers $N$ and $M (1 \le N \le 500, 0 \le M \le 2,000)$ in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in $[0, N)$ separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.

输出格式

There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.

题目大意

题目描述

$N$ 个小朋友（编号为 $0,1,2,…,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。

数据范围

$1 \le N \le 500$，$1 \le M \le 2000$。

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