3540. [POJ 2912]剪刀石头布

【题目描述】

n个人进行m轮剪刀石头布游戏(0<n<=500,0<=m<=2000)，接下来m行形如x, y, ch的输入，ch='='表示x, y平局，ch='>'表示x赢y，ch='<'表示x输y, 但是我们不知道x, y的手势是什么; 其中有一个人是裁判，它可以出任意手势，其余人手势相同的分一组，共分为三组，可以存在空组，也就是说除了裁判外，其余人每一次出的手势都相同，问能不能确定裁判是几号，如果能，输出最少在第几轮可以确定；如果裁判可能有多个,就输出"Can not determine",没有就输出"Impossible".

【输入格式】

输入包含多组数据,每组数据第一行包含两个整数N，M表示N个孩子进行了M轮游戏。

下面是M行，每行包含[0，N]中的两个整数，由一个符号分隔。两个整数表示两个孩子的ID。符号可以是“=”、“>”或“<”。

【输出格式】

每组数据输出一行

如果裁判可能有多个,就输出"Can not determine",没有就输出"Impossible"。

如果可以找到裁判，打印裁判的ID，以及可以唯一确定裁判的最少轮数。

【样例输入】

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