Skeletons

You just started your own clan in an online strategy game. Every clan owns several villages, and one-directional roads connect pairs of villages. The two ends of a road may be the same village. All roads have the same length. You can produce troops in your clan and then attack another clan. Your favorite troops are the wall breakers, skeletons that carry bombs, run, and blow up the walls of enemy villages. The skeletons are smart, and you cannot predict how they will move.

An attack goes like this. You pick the enemy clan, put one skeleton in every village of that clan, choose a positive real number $t$ for the bomb timers, and press the attack key. Every skeleton immediately picks one enemy village as its target, and the targets are picked so that every village is the target of exactly one skeleton. The starting village and the target village of a skeleton may be the same. During the attack all skeletons run at the same constant speed without stopping. They pass roads only in the allowed direction, and a skeleton may pass the same road several times. After exactly $t$ seconds every bomb goes off and all skeletons explode.

The attack succeeds if every skeleton explodes on its own target village. A skeleton is smart enough to pick a route that puts it on its target exactly $t$ seconds later whenever such a route exists. Given a list of clans, find the clans for which you can choose a timer value that makes the attack succeed no matter how the skeletons split the targets among themselves.

The input holds the descriptions of several clans. The first line of each clan holds the number of villages $n$ and the number of roads $m$ ($1 \le n \le 50000$, $1 \le m \le 100000$). The villages are numbered $1$ through $n$. Each of the next $m$ lines holds two space separated integers $x$ and $y$, a one-directional road from village $x$ to village $y$. Several roads may connect the same two villages, and a road may start and end at the same village. The last line of the input is 0 0, and you do not process it.

Print one line for each clan. Print Y if you can choose a timer value $t$ that guarantees the success of the attack, and N otherwise.