题号：NC24610
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
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
and 
(1 <= <= N; 1 <= <= N). The votes are called 
( in {'Y', 'N'}) and 
( 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
* 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:
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
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:
输出描述:
* 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'.