Cow Parliament

Problem Source

USACO 2011 Jan

Problem Description

Deeply unhappy with Farmer John's leadership, the cows have left the farm and formed a Cow Parliament.

The parliament operates on the principle that "every cow can get what she wants," establishing the following voting system: $M$ cows present vote on $N$ bills. Each cow casts exactly two votes, on two bills $B_i, C_i$, as Y (yes) or N (no), meaning approval and disapproval respectively. Finally, the bills are decided as follows: for each cow, at least one of her two votes must agree with the final outcome. For example, if Bessie votes yes (Y) on bill 1 and no (N) on bill 2, then in any valid bill-passing plan, bill 1 must be Y or bill 2 must be N (or both).

Given each cow's votes, your job is to determine which bills can pass and which cannot. If no such plan exists, output IMPOSSIBLE. For a bill that passes in every valid plan, output Y; for one that fails in every valid plan, output N; otherwise output the question mark ?.

Input Format

The first line contains two integers $N, M$ ($1 \leq N \leq 1000,\ 1 \leq M \leq 4000$).

The next $M$ lines each describe one cow's voting plan, giving in turn the index of the first bill and whether she approves, then the index of the second bill and whether she approves.

Output Format

If there is a solution, output a string of length $N$ consisting of Y, N, ?, indicating in order whether each bill will pass; otherwise output IMPOSSIBLE.

Sample Input

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

Sample Output

YN?

Constraints

• $1 \leq N \leq 1000$
• $1 \leq M \leq 4000$