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 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
"merges" in the form
indicating that the friend group containing
has joined with the friend group containing
to form one unified friend group. However, Frank may sometimes give Pam unnecessary information (i.e. if
and
are already in the same friend group).
Help Pam determine which notifications from Frank are unnecessary.
Constraints
In all test cases, ,
,
Subtask 1 [50%]
,
Subtask 2 [50%]
No additional constraints.
Input Specification
First line: (the number of students) and
(the number of merge notifications).
Next
lines:
and
indicating that the friend group containing
is merging with the friend group containing
.
Output Specification
For each of the 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 and
have been merged as follows:
Frank then notifies Pam that and
have merged as follows:
Frank then notifies Pam that and
have merged, but this is unnecessary information since
and
are already in the same friend group.
Comments