OpenKattis
Extrauppgifter [converted from problem group]

Start

2020-03-18 16:00 AKDT

Extrauppgifter [converted from problem group]

End

2021-03-18 16:00 AKDT
The end is near!
Session is over.
Not yet started.
Session is starting in -257 days 12:29:33

Time elapsed

6180:29:33

Time remaining

2579:30:27

Problem S
Union-Find

Input

The first line of input consists of two integers $N$ and $Q$, where $1 \le N \le 1\, 000\, 000$ is the number of elements in the base set and $0 \le Q \le 1\, 000\, 000$ 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 $N-1$.

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