|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
K - Kids’ Wishes
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
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 \leq K \leq 10^9)$ and the number of wishes $(0 \leq W \leq 10^5)$. 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 \leq A, B \leq 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 $\texttt{‘Y’}$ if it is possible to arrange a
circle in such a way that all kids’ wishes are satisfied, or an uppercase $\texttt{‘N’}$ otherwise.
Sample test(s)
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
Output
N
Y
Y