After analyzing her school's friend groups for a while, Pam has gotten Frank to tell her exactly which friend groups are being joined.

There are ~N~ students in Pam's school. Each of them start off as lone students (each student is their own friend group). Throughout the school year, Frank notifies Pam of ~K~ "merges" in the form ~(u_i, v_i)~ indicating that the friend group containing ~u_i~ has joined with the friend group containing ~v_i~ to form one unified friend group. However, Frank may sometimes give Pam unnecessary information (i.e. if ~u_i~ and ~v_i~ are already in the same friend group).

Help Pam determine which notifications from Frank are unnecessary.

Constraints

In all test cases, ~1 \le N \le 10^5~, ~1 \le u_i, v_i \le N~, ~1 \le K \le 5 \times 10^5~

Subtask 1 [50%]

~1 \le N \le 500~, ~1 \le K \le 1000~

Subtask 2 [50%]

No additional constraints.

Input Specification

First line: ~N~ (the number of students) and ~K~ (the number of merge notifications). Next ~K~ lines: ~u_i~ and ~v_i~ indicating that the friend group containing ~u_i~ is merging with the friend group containing ~v_i~.

Output Specification

For each of the ~K~ merge notifications, output Y if the merge notification was necessary or N if it was unnecessary.

Sample Input

3 3
1 2
2 3
1 3

Sample Output

Y
Y
N

Explanation for Sample Case

Initially everyone is a lone student:

Frank notifies Pam that ~1~ and ~2~ have been merged as follows:

Frank then notifies Pam that ~2~ and ~3~ have merged as follows:

Frank then notifies Pam that ~1~ and ~3~ have merged, but this is unnecessary information since ~1~ and ~3~ are already in the same friend group.