Description

最近，XMU的神经病XXX迷上了一款益智小游戏，在这个游戏中XXX将当任自来水公司的老板，负责安排自来水厂和自来水管的调度问题。

现在XXX手上有N个自来水厂和N个需要用水的大工厂，我们假设编号从1开始到2*N，且奇数编号表示自来水厂，偶数编号表示需要用水的大工厂，XXX还能修建 N+M 条单向的自来水管道，从自来水厂指向大工厂。现在XXX使用最笨的方式，对于每个自来水厂 A=2k+1，他修建了一条单向自来水管道指向大工厂B=2k+2，现在他还剩余一些资金，能够修建M条单向自来水管道，于是他就瞎修一通，也看不出来有什么用。于是聪明的你看不下去了，想要考考他，这里面哪些大工厂是安全牢靠的。

这里的安全牢靠指的是，如果自来水厂 A=2k+1 到大工厂 B=2k+2 的直接相连的自来水管道断裂时，仍然有一种供水的方案，在每个自来水厂只对一个大工厂供水的情况下，使得每个大工厂都能获得供水。

Format

Input

输入的第一行为两个整数N和M,(1<=N<=100000,M<=2*N)，如上所述
接下来M行，每行两个整数X和Y，表示编号为X的自来水厂有一条单向管道到编号为Y的大工厂。数据保证X为自来水厂且Y为大工厂。

Output

输出N行，每行表示第i个大工厂是不是安全可靠的，是输出Y，否则输出N

Sample 1

Input

2 1
3 2

Output

N
N

Sample 2

Input

2 2
3 2
1 4

Output

Y
Y

Limitation

1s, 128MB for each test case.

Hint

Source

Coolxxx