[Usaco2011 Jan]奶牛议会

由于对 Farmer John 的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以「每头牛都可以获得自己想要的」为原则，建立了下面的投票系统。

到场的 $M$ 只奶牛会给 $N$ 个议案投票。每只奶牛会对恰好两个议案 $B_i$ 和 $C_i$ 投出「是」或「否」（输入文件中的 Y 和 N），它们的投票结果分别为 $VB_i$ 和 $VC_i$。

最后，议案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。例如 Bessie 给议案 $1$ 投了赞成 Y，给议案 $2$ 投了反对 N，那么在任何合法的议案通过方案中，必须满足议案 $1$ 是 Y 或者议案 $2$ 是 N（或者同时满足）。

给出每只奶牛的投票，你的工作是确定哪些议案可以通过，哪些不能：

• 如果不存在这样一个方案，输出 IMPOSSIBLE；
• 如果至少有一个解，则对每个议案输出一个字符：
  • Y：如果在每个解中，这个议案都必须通过；
  • N：如果在每个解中，这个议案都必须驳回；
  • ?：如果有的解中这个议案可以通过，有的解中这个议案会被驳回。

考虑如下的投票集合：

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

下面是两个可能的解：

• 议案 $1$ 通过（满足奶牛 $1, 3, 4$）；
• 议案 $2$ 驳回（满足奶牛 $2$）；
• 议案 $3$ 可以通过也可以驳回（这就是有两个解的原因）。

事实上，上面的问题也只有两个解。所以，输出的答案是 YN?。

输入格式

第一行两个空格隔开的整数 $N$ 和 $M$。

第 $2$ 到第 $M+1$ 行，第 $i+1$ 行描述第 $i$ 只奶牛的投票方案：$B_i$，$VB_i$，$C_i$，$VC_i$。

输出格式

一行一个含有 $N$ 个字符的串，第 $i$ 个字符要么是 Y（第 $i$ 个议案必须通过），要么是 N（第 $i$ 个议案必须驳回），要么是 ?。

如果无解，输出 IMPOSSIBLE。

样例输入

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

样例输出

YN?

数据范围

• $1\le N\le 1000$；
• $1\le M\le 4000$；
• $1\le B_i\le N$，$1\le C_i\le N$；
• $VB_i, VC_i\in\{\text{Y}, \text{N}\}$。

来源与许可

本题为 USACO 2011 Jan 试题「奶牛议会」，题面与测试数据整理自 BZOJ 2199。

样例 1

输入

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

输出

YN?