KING - King

no tags 

The Nlogonia Kingdom needs a new king. Differently from other monarchy kingdoms, where the king’s choice is hierarchical, at Nlogonia any citizen can apply for the post and the whole population can vote on those who applied. However, with these conditions, a big problem arises: every citizen would probably apply and vote for itself.

In order to solve this problem the Nlogonia council decided to split the voting process in two phases. In the first phase, known as constraint phase, every citizen must write two constraints about another two candidates. A constraint can be of one of the following two types: a reliability constraint, which means that the citizen trusts another citizen and wishes that it takes place in the second phase of the voting process; an unreliability constraint, which means that the citizen doesn’t trust another one and wishes that he doesn’t take place in the second phase of the process.

The council decided that at least one of the constraints of every citizen must be satisfied in order to choose the group of candidates that can go forward to the second phase. The citizen cannot give itself a reliability constraint. The second phase of the process is a simple voting process where every citizen chooses between one of the candidates that remained from the first phase. Your job is to determine if it is possible to satisfy at least one of the two constraints of every citizen, even if it means that no candidate remains for the second phase, in this case the council decides who must be the king.

Input

Each test case is described using several lines. The first line contains one integer N representing the number of citizen in the Nlogonia Kingdom (3 ≤ N ≤ 1000). The candidates are identified by different integer from 0 to N-1. Each of the next N lines describes the two constraints of a citizen, and each one starts with an uppercase letter that is either ‘R’ or ‘U’, where ‘R’ indicates a reliability constraint and ‘U’ indicates a unreliability constraint, followed by a integer C (0 ≤ C < 1000) representing the candidate that the citizen gave the constraint. The two constraints will be separated by single space.

The last test case is followed by a line containing one zero.

Output

For each test, use the output uppercase ‘Y’ if it is possible to satisfy at least one constraint for each citizen and ‘N’ if it is not.

Example

Input:
3
R1U0
U2R1
R2R0
4
R1U0
R0U1
R0R1
U0U1 0 Output: Y
N

hide comments
guoyu1098: 2013-12-27 02:00:32

The last test case is followed by a line containing one zero.

The real input is this one:

3
R 1 U 0
U 2 R 1
R 2 R 0
4
R 1 U 0
R 0 U 1
R 0 R 1
U 0 U 1
0

(test): 2012-02-27 04:31:50

When the citizen does give itself a reliability constraint (appears in the actual test cases), what should we do?

Robin Lee: 2012-02-10 16:43:57

Please give valid example inputs. This should be terminated with a 0.

Suit up!: 2012-02-10 16:17:51

The real input is this one:

3
R 1 U 0
U 2 R 1
R 2 R 0
4
R 1 U 0
R 0 U 1
R 0 R 1
U 0 U 1


Added by:Paulo Costa
Date:2012-02-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64