K :: Kids’ Wishes

Time Limit: 1 Second    Memory Limit: 65536 KB

Kevin is a kid. He has lunch at school together with many more kids. They use to go outdoors and have lunch 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 problems arranging the circle because some kids wish to sit down next to other kids. Each kid may wish to sit down next to at most two other kids, because each kid has just two neighbors in the circle. The teacher wants to know whether it is possible to arrange the circle in such a way that all kids’ wishes are satisfied. You clean up the place when the lunch ends. Since you want to finish your work as early as possible, help the teacher in answering that question.

Input

Each test case is given using several lines. The first line contains two integers K and W representing respectively the number of kids (3 ≤ K ≤ 10⁹) and the number of wishes (0 ≤ W ≤ 10⁵). Kids are identified with numbers between 1 and K. Each of the next W lines describes a different wish using two distinct integers A and B (1 ≤ A,B ≤ K); these values represent that kid A wishes to sit down next to kid B. Each kid has 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 a circle in such a way that all kids’ wishes are satisfied, or an uppercase ‘N’ otherwise.

Sample 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

Sample Output

N
Y
Y

Submit

Source: Latin American Regional Contest 2010