奶牛议会

题目来源

USACO2011 Jan

题目描述

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

议会以“每头牛 都可以获得自己想要的”为原则，建立了下面的投票系统：$M$ 只到场的奶牛会给 $N$ 个议案投票。每只奶牛会对恰好两个议案 $B_i, C_i$ 投出 Y 或 N ，分别表示赞成和反对。最后，议案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。例如 Bessie 给议案 $1$ 投了赞成 Y，给议案 $2$ 投了反对 N，那么在任何合法的议案通过方案中，必须满足议案 $1$ 必须是 Y 或者议案 $2$ 必须是 N，或者同时满足。

给出每只奶牛的投票，你的工作是确定哪些议案可以通过，哪些不能。如果不存在这样一个方案，输出 IMPOSSIBLE。对于一个议案，如果在所有方案里面都能通过，输出 Y。如果在所有方案里面都不能能通过，输出 N，否则输出问号 ?。

输入格式

第一行，两个整数 $N, M(1\leq N\leq 1000, 1\leq M\leq 4000)$。

接下来 $M$ 行，每行描述一个奶牛的投票方案，依次次给出第一个议案的编号和是否赞成，第二个议案的编号和是否赞成。

输出格式

如果有解，输出一个长度为 $N$ 的包含 YN? 字符串，依次表示每个议案是否会被通过，否则输出 IMPOSSIBLE。

样例输入

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

样例输出

YN?