Description：

每头牛投两票（赞同或反对），要求每头牛至少有一票与最终结果相符，判断是否有解，判断每个议案是否结果确定，如果确定结果是什么。

$1\le n \le 1000$ $1\le m \le 4000$

Solution：

$2-SAT$ 判断答案，不选这个向选另一个连边，代表两个中必须选一个。

最后判断是否有解可以枚举每个议案，分别 $dfs$ 通过和不通过两个点并将所经过的点打上标记，代表如果通过/不通过则哪些通过情况是可以确定的，如果有一个议案的通过不通过同时被打上标记，则这个方案不合法，得到了每个议案是否能通过/不通过，于是就可以判断了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

#define MAXM 1010

#define MAXN 4010

inline int get()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	while(c != 'Y' && c != 'N')c = getchar();

	return (((res - 1) << 1) | (c == 'Y' ? 1 : 0));

}

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int dfn[MAXM << 1],low[MAXM << 1],tot = 0;

stack<int> s;

bool v[MAXM << 1];

int ins[MAXM << 1],scc = 0;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(low[k] == dfn[k])

	{

		int t;

		++scc;

		do

		{

			t = s.top();s.pop();

			v[t] = false;ins[t] = scc;

		}while(t != k);

	}

	return;

}

char ans[MAXM];

bool mark[MAXM << 1];

void dfs(int k)

{

	mark[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!mark[e[i].to])

		{

			dfs(e[i].to);

		}

	}

	return;

}

bool check(int k)

{

	memset(mark,false,sizeof(mark));

	dfs(k);

	for(int i = 1;i <= m;++i)

	{

		if(mark[((i - 1) << 1 | 1)] && mark[(i - 1) << 1])return false;

	}

	return true;

}

int main()

{

	scanf("%d%d",&m,&n);

	int a,b;

	for(int i = 1;i <= n;++i)

	{

		a = get(),b = get();

		add(a ^ 1,b);

		add(b ^ 1,a);

	}

	for(int i = 0;i < 2 * m;++i)

	{

		if(dfn[i] == 0)tarjan(i);

	}

	bool tag = true;

	for(int i = 1;i <= m;++i)

	{

		bool p = check(((i - 1) << 1) | 1),q = check((i - 1) << 1);

		if(p && q)ans[i] = '?';

		else if(p && !q)ans[i] = 'Y';

		else if(!p && q)ans[i] = 'N';

		else{tag = false;break;}

	}

	if(tag)

	{

		for(int i = 1;i <= m;++i)putchar(ans[i]);puts("");

	}

	else puts("IMPOSSIBLE");

	return 0;

}