[USACO11JAN] The Continental Cowngress G

> 简述 : > 给出 $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` 如果在每个解中，这个法案都必须驳回。 - `?` 如果有的解这个法案可以通过，有的解中这个法案会被驳回。

Displeased with Farmer John's leadership, the cows have seceded from the farm and have formed the first Continental Cowngress. Built on the principle of 'every cow gets something they want,' they've decided on the following voting system: The M (1 <= M <= 4000) cows in attendance will vote on N (1 <= N <= 1,000) legislative bills. Each cow casts a 'yes' or 'no' vote (denoted as 'Y' or 'N' in the input file) on exactly two (distinct) bills B\_i and C\_i (1 <= B\_i <= N; 1 <= C\_i <= N). The votes are called VB\_i (VB\_i in {'Y', 'N'}) and VC\_i (VC\_i in {'Y', 'N'}) respectively. Finally, the bills are to be passed or not in such a way that every cow gets her way on at least one of her votes. For example, if Bessie votes 'yes' on Bill 1, and 'no' on Bill 2, then in any valid solution, it must be the case that either Bill 1 gets passed or Bill 2 gets rejected (or both). Given the votes of each of the cows, it's your job to figure out which bills will be passed and which bills will be rejected in order to conform to the rules above. If there is no solution, print 'IMPOSSIBLE'. If there is at least one solution, then for each bill, display: Y if in every solution this bill passes N if in every solution this bill fails ? if there are solutions where this bill passes and solutions where it does not pass Consider the following set of votes (two for each cow): ``` - - - - - BILL - - - - - 1 2 3 Cow 1 YES NO Cow 2 NO NO Cow 3 YES YES Cow 4 YES YES ``` From this, two solutions satisfy every cow: \* Bill 1 passes (this then satisfies cows 1, 3, and 4) \* Bill 2 fails (this then satisfies cow 2) \* Bill 3 could pass or fail (and this is the reason there are two solutions) In fact, these are the only two solutions, so the answer is the three character string below:

\* Line 1: Two space-separated integers: N and M \* Lines 2..M+1: Line i+1 describes cow i's votes with four space-separated fields -- an integer, a vote, another integer, and another vote: B\_i, VB\_i, C\_i, VC\_i

\* Line 1: A string with N characters, where the ith character is either a 'Y' if the ith bill must pass, an 'N' if the ith bill must fail, or a '?' if it cannot be determined whether the bill passes from these votes. If there is no solution which satisfies every cow, then output the single line 'IMPOSSIBLE'.

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

YN?