记录编号	23696	评测结果	AAAAAAAAAA
题目名称	奶牛议会	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	0.329 s
提交时间	2011-03-17 16:04:02	内存使用	0.79 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXM=4001;
const int MAXN=1111;

struct edge
{
	int t;
	edge *p;
}e[MAXM*10],*v[MAXN];

struct cow
{
	int f1,f2,c1,c2;
}C[MAXM];

int es=-1,n,m,i,j,k,re[MAXN],ans[MAXN],Q[MAXM*10];
char ch;
bool b[MAXM],flag=false;

inline void addedge(int i,int j)
{
	e[++es].t=j; e[es].p=v[i]; v[i]=e+es;
}

bool pd()
{
	int h,t;
	h=t=1;
	Q[1]=i;
	while (t>=h)
	{
		k=Q[h];
		for (edge *x=v[k];x;x=x->p)
		{
			if (C[x->t].f1==k && C[x->t].c1!=re[k])
			{
				if (re[C[x->t].f2]!=-1 && C[x->t].c2!=re[C[x->t].f2]) return false;
				if (re[C[x->t].f2]==-1)
				{
					++t;
					Q[t]=C[x->t].f2;
					re[C[x->t].f2]=C[x->t].c2;
				}
			}
			if (C[x->t].f2==k && C[x->t].c2!=re[k])
			{
				if (re[C[x->t].f1]!=-1 && C[x->t].c1!=re[C[x->t].f1]) return false;
				if (re[C[x->t].f1]==-1)
				{
					++t;
					Q[t]=C[x->t].f1;
					re[C[x->t].f1]=C[x->t].c1;
				}
			}
		}
		++h;
	}
	return true;
}

int main()
{
	freopen("cowngress.in","r",stdin);
	freopen("cowngress.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		ans[i]=-1;
	for (i=1;i<=m;i++)
	{
		scanf("%d%c%c",&j,&ch,&ch);
		C[i].f1=j;
		if (ch=='N') C[i].c1=0;
		else C[i].c1=1;
		addedge(j,i);
		scanf("%d%c%c",&j,&ch,&ch);
		C[i].f2=j;
		if (ch=='N') C[i].c2=0;
		else C[i].c2=1;
		addedge(j,i);
	}
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
			re[j]=-1;
		re[i]=1;
		if (pd())
		{
			ans[i]=1;
		}
		for (j=1;j<=n;j++)
			re[j]=-1;
		re[i]=0;
		if (pd())
		{
			if (ans[i]==-1) ans[i]=0;
			else ans[i]=2;
		}
		else if (ans[i]==-1)
		{
			printf("IMPOSSIBLE\n");
			return 0;
		}
	}
	for (i=1;i<=n;i++)
	{
		if (ans[i]==1) printf("Y");
		if (ans[i]==2 || ans[i]==-1) printf("?");
		if (ans[i]==0) printf("N");
	}
	printf("\n");
	return 0;
}