Rochambeau
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 6480 Accepted: 2174
Description

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

Input contains multiple test cases. Each test case starts with two integers N and M (1 ≤ N ≤ 500, 0 ≤ M ≤ 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.

Output

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.

Sample Input

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
Sample Output

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

题目大意：有n个孩子在玩石头剪刀布的游戏（石头吃剪刀，剪刀吃布，布吃石头，怎么样是不是想起来什么），然后他们被分成三组，相同组的成员每次出的手势都是一样的，其中有一个裁判，裁判的手势是可以随意出的，现在给你他们每次pk的结果要你找裁判是谁，你发现裁判是在第几行。
思路：这个题我看大佬的思路写出来的，用的是逆向思维，一开始我是这样想的每次输入都用并查集并起来，如果某次出现冲突，那么裁判肯定会在他们中间，但是这样存在一些问题，因为裁判有可能在不确定的情况下每个人都是裁判，这种情况是无法将裁判找出来的，而且冲突一般是两个节点，但是裁判只有一个，这样就存在问题。
所以我先把所有的边权存下来，因为n的范围只有5000所以枚举每个节点是裁判的情况，然后如果当前枚举是裁判，会有两种情况，第一种剩下的节点合并不存在冲突，说明该节点可能确实是裁判，第二种可能剩下的节点存在冲突，只有裁判才能任意出手势，也就是说当前节点一定不是裁判，用这个思维去做就行了。。并查集路径压缩和合并公式和食物链基本是一样的。。
有一个wa点坑了我好久，如果两个节点的根节点相同那么要进行合并操作，但是合并操作还要判断一下当前节点！=上一次节点，因为会出这样的数据卡你， 0<1,0<1，所以要把重边考虑进来，代码：

#include<iostream>
#include<algorithm> 
#include<cstdio>
#include<cstring>
using namespace std;

struct node{
	int u,v,w;
}a[2020];
int f[1010],r[1010];
int find(int x){
	if(x!=f[x]){
		int t=f[x];
		f[x]=find(f[x]);
		r[x]=(r[x]+r[t])%3;
	}
	return f[x];
}
int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		char ch;
		for(int i=1;i<=m;i++){
			scanf("%d%c%d",&a[i].u,&ch,&a[i].v);
			if(ch=='=')a[i].w=0;
			if(ch=='<')a[i].w=1;
			if(ch=='>')a[i].w=2;
		}
		int judge;int index=0;int num=0;// num裁判的个数 judge 表示裁判的标号，index裁判被找出来的最小行 
		for(int i=0;i<n;i++){//枚举每个人是裁判的情况
		      for(int j=0;j<n;j++){//每次枚举建立的树是不一样的因此每次都要初始化一下 
		    		f[j]=j;r[j]=0;
				}
		    bool flag=true;//判断当前枚举是否是裁判 
		    for(int j=1;j<=m;j++){
		    	int u=a[j].u;int v=a[j].v;int w=a[j].w;
		    	if(u==i||v==i){continue;}//把与裁判有关的全部pass掉，剩下的如果不存在冲突那个这个裁判可能是真的 
				//如果剩下的并起来出现冲突说明当前裁判是假的
				int fx=find(u);
				int fy=find(v);
				if(fx==fy&&(r[u]-w+3)%3!=r[v]){//因为把跟裁判pk的全部pass了，这个时候还冲突只能说裁判选错了或者不止一个裁判 (r[u]-w+3)%3!=r[v]表示不能出现
				//相同情况，比如0<1 0<1这样出现两次就错了 
					index=max(index,j);//如果只有一个裁判，那么所有不是裁判的最大边就是裁判裁判的边
					flag=false;//存在冲突说明裁判可能不止一个或者当前裁判是假的 
					break;
				}else{
					f[fx]=fy;
					r[fx]=(w+r[v]-r[u]+3)%3;
				} 
			} 
			if(flag){
				num++;
				judge=i;//保存裁判编号 
			}
		}
		if(num>1){
			cout<<"Can not determine"<<endl;
		}else if(num==1){
			cout<<"Player "<<judge<<" can be determined to be the judge after "<<index<<" lines"<<endl;
		}else{
			cout<<"Impossible"<<endl;
		}
	}
}