P3007 [USACO11JAN] The Continental Cowngress G

由于对农场主约翰的领导不满，奶牛们已经从农场中分离出来，并成立了第一个大陆奶牛议会。基于「每头奶牛都能得到她想要的东西」这一原则，她们决定采用以下投票系统： 出席的 $M$ 头奶牛将对 $N$ 项立法议案进行投票。每头奶牛对两个（不同的）议案 $B_i$ 和 $C_i$ 分别投下「赞成」或「反对」票（在输入文件中用 `Y` 或 `N` 表示）。这些投票分别称为 $VB_i$ 和 $VC_i$。 最终，议案的通过与否必须满足每头奶牛至少有一个投票结果符合她的意愿。例如，如果 Bessie 对议案 $1$ 投了「赞成」票，对议案 $2$ 投了「反对」票，那么在任何有效的解决方案中，要么议案 $1$ 通过，要么议案 $2$ 被否决（或者两者都满足）。 给定每头奶牛的投票情况，你的任务是找出哪些议案将被通过，哪些议案将被否决，以符合上述规则。如果没有解决方案，请输出 `IMPOSSIBLE`。如果至少有一个解决方案，那么对于每个议案，显示： `Y` 如果在每个解决方案中该议案都通过 `N` 如果在每个解决方案中该议案都被否决 `?` 如果存在一些解决方案中该议案通过，而在另一些解决方案中该议案没有通过 考虑以下投票集（每头奶牛投两票）： |编号|$1$|$2$|$3$| |:-:|:-:|:-:|:-: |奶牛 $1$|赞成|反对 |奶牛 $2$|反对|反对 |奶牛 $3$|赞成||赞成 |奶牛 $4$|赞成|赞成 由此，两个解决方案满足每头奶牛： + 议案 $1$ 通过（这满足了奶牛 $1$、$3$ 和 $4$） + 议案 $2$ 被否决（这满足了奶牛 $2$） + 议案 $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`。

对于 $100\%$ 的数据，$1\le M\le4000$，$1\le N\le1000$，$1\le B_i,C_i\le N$，$VB_i,VC_i\in\{Y,N\}$。 （本题由 ChatGPT 4o 翻译）