Asking for Money

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given who each person asks for money, find every person whose two requests can both fail because those people already paid someone else.

Level: Medium5 of 10
Topics: Graph, DFS, BFS
Solved: No attempts yet

Problem

The International Commission for the Prevention of Cons is studying the possible effects of a pyramid scheme in a town. The scheme works as follows. Someone asks a person for $1 and tells them to ask two other people for $1 each, and to tell each of them to ask two others in the same way. The victim thinks they will earn $1. Since the number of people in the world is finite, not everyone can earn money this way, so this is a con.

The $N$ people in town are susceptible to the con. Each of them is willing to give $1 and later ask two other people for money. However, each person participates only once. If they are asked for money again, they will neither give it nor ask anyone. Once a person is asked for money, they give it immediately, but they may wait some time before asking the other two people. The con starts when someone from outside the town asks a person in the town for money. This triggers a sequence of requests within the town.

For example, the picture below shows a town with five people. An arrow from $A$ to $B$ means that $A$ asks $B$ for money.

In this example, $B$ can lose money. Consider the following scenario.

Someone from outside the town asks $A$ for money.
$A$ asks $B$ for money.
$A$ asks $C$ for money.
$C$ asks $D$ for money.
$B$ asks $C$ for money.
$B$ asks $D$ for money.

When $B$ asks $C$ and $D$ for money, they do not give it to $B$ , because they have already given money to someone else.

For each person in the town, you know whom they ask for money. Determine who in the town can lose money.

Input

The first line contains an integer $N$ ( $3 \le N \le 1000$ ), the number of people in the town. Each person is identified by a distinct integer from $1$ to $N$ . For $i = 1, 2, \dots, N$ , the $i$ -th of the next $N$ lines contains two integers $X_i$ and $Y_i$ ( $1 \le X_i, Y_i \le N$ , $X_i, Y_i \ne i$ , and $X_i \ne Y_i$ ), meaning that person $i$ asks persons $X_i$ and $Y_i$ for money.

Output

Output a single line containing a string of length $N$ . The $i$ -th character is an uppercase Y if person $i$ can lose money, and an uppercase N otherwise.

Examples2

Example 1
Input
```
5
2 3
3 4
4 5
5 1
1 2
```
Expected output
```
YYYYY
```
Example 2
Input
```
4
2 3
3 4
2 4
2 3
```
Expected output
```
NYYY
```