Friend Groups 2

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 3.5s
Memory limit: 128M

Author:
Problem types

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: 1

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

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

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.


Comments

There are no comments at the moment.