题目描述

简述 :

给出 $n$ 个法案， $m$ 头牛的意见， 每头牛会表决两次。

每次表决格式为 i Y 表示“支持 $i$ 号法案”或 i N 表示“反对 $i$ 号法案”。

最终，每头牛至少要有一个表决被满足。不可能成立的话输出 IMPOSSIBLE，否则输出方案。

由于对 Farmer John 的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。

议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统： $M$只到场的奶牛 ( $1\le M\le 4000$ ) 会给 $N$ 个议案投票 ( $1\le N\le 1,000$ ) 。每只奶牛会对恰好两个议案 $B_i$ 与 $C_i$ ( $1\le B_i \le N$ ; $1 \le C_i \le N$ ) 投出“是”或“否”（输入文件中的 Y 和 N ）。

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

你的工作是确定哪些法案可以通过，哪些不能。

如果不存在这样一个方案， 输出 IMPOSSIBLE。

如果至少有一个解，对于每个法案输出：

• Y 如果在每个解中，这个法案都必须通过。
• N 如果在每个解中，这个法案都必须驳回。
• ? 如果有的解这个法案可以通过，有的解中这个法案会被驳回。

输入格式

第一行输入两个正整数 $n,m$

接下来 $m$ 行每行四个内容格式如下

u op1 v op2，其中 $u, v$ 为法案编号，op1, op2 的值为 Y 或 N，即为通过该法案或驳回改法案。

输出格式

若没有合法方案输出 IMPOSSIBLE，否则输出一个形如 YN? 的字符串。

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

YN?