记录编号	56404	评测结果	AAAAAAAAAA
题目名称	奶牛议会	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.224 s
提交时间	2013-03-29 10:49:19	内存使用	14.75 MiB

/*  
by   wyfenger
add	 wyfenger.tk 
prob cowngress
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
struct node{
	int nex;
}a[4001];
struct edge{
	int nex,y;
}e[500001];
struct numm{
	int num,v;
}aa[8001][2];
int n,m,p;
bool f[2001];
int ans[2001][1001];
int re[1001];

void add(int x,int y){
	p++;
	e[p].nex=a[x].nex;
	a[x].nex=p;
	e[p].y=y;
}
void init(){
	freopen("cowngress.in","r",stdin);
	freopen("cowngress.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	p=0;
	int x,y;
	char ch1,ch2;
	for (int i=1;i<=m;i++){
		scanf("%d %c %d %c",&x,&ch1,&y,&ch2);
		aa[i][0].num=x;
		aa[i][0].v=(ch1=='Y');
		aa[i][1].num=y;
		aa[i][1].v=(ch2=='Y');
	}
	
	for (int i=1;i<=n;i++)
		for (int j=0;j<=1;j++)
			
			for (int ii=1;ii<=m;ii++)
				for (int jj=0;jj<=1;jj++)
					
					if (aa[ii][jj].num==i && aa[ii][jj].v!=j){
						x=aa[ii][!jj].num;
						y=aa[ii][!jj].v;
						add((i-1)*2+j+1,(x-1)*2+y+1);
					}
}
int cul(int i){
	for (int j=1;j<=n*2;j+=2){
			int tmp=(j+1)/2;
			if (!f[j] && !f[j+1]) ans[i][tmp]=-2;
			if (f[j] && !f[j+1]) ans[i][tmp]=-1;
			if (!f[j] && f[j+1]) ans[i][tmp]=1;
			if (f[j] && f[j+1]) return 0;
		}
	return 1;
}
void dfs(int s){
	f[s]=true;
	int t=a[s].nex;
	while (t){
		if (!f[e[t].y]){
			dfs(e[t].y);
		}
		t=e[t].nex;
	}
}
void work(){
	for (int i=1;i<=n*2;i++){
		
		memset(f,false,sizeof(f));
		dfs(i);
		
		ans[i][0]=cul(i);
		
	}
	for (int i=1;i<=n;i++)
		re[i]=-2;
	for (int i=1;i<=n*2;i++)
		if (ans[i][0])
			for (int j=1;j<=n;j++){
				if (re[j]==-2)
					re[j]=ans[i][j];
				else{
					if (re[j]==-1 && ans[i][j]==1) re[j]=0;
					if (re[j]==1 && ans[i][j]==-1) re[j]=0;
					//if (ans[i][j]==0) re[j]=0;
				}
			}
	for (int i=1;i<=n;i++)
		if (re[i]==-2){
			printf("IMPOSSIBLE");
			return ;
		}
	for (int i=1;i<=n;i++){
		if (re[i]==-1) printf("N");
		if (re[i]==1)  printf("Y");
		if (re[i]==0)  printf("?");
	}
}

int main()
{
	init();
	work();
	return 0;
}