Hide

Problem T
Union-Find

Input

The first line of input consists of two integers N and Q, where 1N1000000 is the number of elements in the base set and 0Q1000000 is the number of operations. Then follow Q lines, one per operation. There are two types of operations:

  • = a b” indicate that the sets containing a and b are joined

  • ? a b” is a query asking whether a and b belong to the same set

In both cases, a and b are distinct integers between 0 and N1.

Output

For each query output a line containing “yes” if a and b are in the same set, and “no” otherwise.

Sample Input 1 Sample Output 1
10 4
? 1 3
= 1 8
= 3 8
? 1 3
no
yes
Sample Input 2 Sample Output 2
4 5
? 0 0
= 0 1
= 1 2
= 0 2
? 0 3
yes
no
Hide

Please log in to submit a solution to this problem

Log in