Kids’ Wishes
| English | Vietnamese |
Gene and Gina have a particular kind of farm. Instead of growing animals and vegetables, as
it is usually the case in regular farms, they grow strings. A string is a sequence of characters.
Strings have the particularity that, as they grow, they add characters to the left and/or to the
right of themselves, but they never lose characters, nor insert new characters in the middle.
Gene and Gina have a collection of photos of some strings at different times during their growth.
The problem is that the collection is not annotated, so they forgot to which string each photo
belongs to. They want to put together a wall to illustrate strings growing procedures, but they
need your help to find an appropriate sequence of photos.
Each photo illustrates a string. The sequence of photos must be such that if si comes imme-
diately before si+1 in the sequence, then si+1 is a string that may have grown from si (i.e., si
appears as a consecutive substring of si+1). Also, they do not want to use repeated pictures,
so all strings in the sequence must be different.
Given a set of strings representing all available photos, your job is to calculate the size of the
largest sequence they can produce following the guidelines above.
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^9) and the number of wishes (0 ≤ W ≤ 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 ≤ 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
output
N Y Y