题目描述(ID:12179)
标题: 议案表决
标签: 图结构
详情: 由于对Farmer John的领导感到极其不悦,奶牛们退出了农场,组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则,建立了下面的投票系统:
M只到场的奶牛 (1 <= M <= 4000) 会给N个议案投票(1 <= N <= 1,000) 。
在N个议案中每只奶牛会对恰好两个议案 Bi and Ci 进行表决(1 <= B_i <= N; 1 <= Ci <= N)投出“是”或“否”(输入文件中的‘Y‘和‘N‘)。(这是个什么鬼规定,只能选两个进行表决)他们的投票结果分别为VBi (VBi in {‘Y‘, ‘N‘}) and VCi (VCi in {‘Y‘, ‘N‘})。

最后,议案会以如下的方式决定:每只奶牛投出的两票中至少有一票和最终结果相符合。

例如Bessie给议案1投了赞成‘Y‘,给议案2投了反对‘N‘,那么在任何合法的议案通过 方案中,必须满足议案1必须是‘Y‘或者议案2必须是‘N‘(或者同时满足)。 给出每只奶牛的投票,你的工作是确定哪些议案可以通过,哪些不能。如果不存在这样一个方案, 输出"IMPOSSIBLE"。如果至少有一个解,输出:

Y: 如果在每个解中,这个议案都必须通过
N: 如果在每个解中,这个议案都必须驳回
?如果有的解这个议案可以通过,有的解中这个议案会被驳回

有四头奶牛对三个议案进行的表决如下:

奶牛 1 : 议案1 YES 议案2  NO
奶牛 2 议案1 NO   议案2 NO
奶牛 3 议案1YES  议案3 YES
奶牛 4 议案1YES  议案2 YES

即:
3 4
1 Y 2 N
1 N 2 N
1 Y 3 Y
1 Y 2 Y
下面是两个可能的解:
解1:
* 议案 1 通过(满足奶牛1,3,4)
* 议案 2 驳回(满足奶牛2)
* 议案 3 通过
解2:
* 议案 1 通过(满足奶牛1,3,4)
* 议案 2 驳回(满足奶牛2)
* 议案 3 驳回


事实上,议案3既可以通过也可以驳回,这就是有两个解的原因,当然上面的问题也只有两个解。所以,输出
YN?

输入格式:
* 第1行:两个空格隔开的整数:N和M * 第2到M+1行:第i+1行描述第i只奶牛的投票方案:B_i, VB_i, C_i, VC_i
输出格式:
* 第1行:一个含有N个字符的串,第i个字符要么是‘Y‘(第i个议案必须通过),或者是‘N‘ (第i个议案必须驳回),或者是‘?‘。 如果无解,输出"IMPOSSIBLE"。
样例:

输入

2 3
1 Y 2 Y
1 Y 2 N
1 N 2 N

输出

YN

输入

10 33
7 Y 1 Y
4 Y 6 Y
7 Y 4 Y
6 Y 1 Y
8 Y 6 N
10 N 5 N
5 N 6 Y
2 Y 4 Y
5 N 6 N
2 Y 3 N
4 Y 8 Y
6 N 7 N
10 N 9 N
5 Y 6 N
10 N 3 Y
1 Y 5 N
4 Y 3 N
7 N 1 N
4 Y 10 N
1 N 9 Y
1 Y 5 N
10 N 4 N
3 N 1 Y
3 N 8 Y
10 N 4 Y
3 N 1 Y
10 N 6 Y
5 N 4 Y
3 Y 7 N
3 N 7 Y
2 Y 7 Y
8 Y 9 N
8 N 10 Y

输出

IMPOSSIBLE

输入

10 30
7 Y 1 Y
4 Y 6 Y
7 Y 4 Y
6 Y 1 Y
8 Y 6 N
10 N 5 N
5 N 6 Y
2 Y 4 Y
5 N 6 N
2 Y 3 N
4 Y 8 Y
6 N 7 N
10 N 9 N
5 Y 6 N
10 N 3 Y
1 Y 5 N
4 Y 3 N
7 N 1 N
4 Y 10 N
1 N 9 Y
1 Y 5 N
10 N 4 N
3 N 1 Y
3 N 8 Y
10 N 4 Y
3 N 1 Y
10 N 6 Y
5 N 4 Y
3 Y 7 N
3 N 7 Y

输出

Y?NYNNN?YN
登录并解答