Kids' Wishes

Time limit1sMemory limit128 MB

Summary

Decide whether all kids can be seated in a circle so every wish (each kid asks for at most two neighbors) is satisfied.

Level: Medium7 of 10
Topics: Graph, Union-find, Implementation, Math
Solved: No attempts yet

Problem

Kevin is a kid. He has lunch at school together with many other kids. They usually go outdoors and eat sitting on the ground. They love to form a big circle in which each kid has exactly two neighbors: one on the left and one on the right. Sometimes the teacher has trouble arranging the circle because some kids wish to sit next to particular other kids. Since each kid has only two neighbors in the circle, a kid may wish to sit next to at most two other kids. The teacher wants to know whether it is possible to arrange the circle so that all kids' wishes are satisfied. Determine whether such an arrangement exists.

Input

The input consists of several test cases. Each test case is given over several lines.

The first line of each test case contains two integers $K$ and $W$ , representing the number of kids ( $3 \le K \le 10^9$ ) and the number of wishes ( $0 \le W \le 10^5$ ), respectively. Kids are identified by numbers from $1$ to $K$ . Each of the next $W$ lines describes one wish using two distinct integers $A$ and $B$ ( $1 \le A, B \le K$ , $A \ne B$ ); this means that kid $A$ wishes to sit next to kid $B$ . Each kid makes at most two wishes.

The last test case is followed by a line containing two zeros.

Output

For each test case, output a single line containing an uppercase 'Y' if it is possible to arrange the circle so that all kids' wishes are satisfied, or an uppercase 'N' otherwise.

Examples3

Example 1

Input

4 3
2 3
1 3
2 1
1000000000 0
3 6
3 2
2 1
1 2
1 3
2 3
3 1
0 0

Expected output

N
Y
Y

Example 2
Input
```
5 1
1 2
0 0
```
Expected output
```
Y
```
Example 3
Input
```
4 3
1 2
2 3
3 4
0 0
```
Expected output
```
Y
```