TTC '18 Contest 1 P4 - A Very Interesting Problem

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

You are given N nodes that are completely separated. You must support the following operations:

  • 1 a b Add an edge between node a and node b. (1 \le a, b \le N, a \neq b). Note that it is not guaranteed node a and node b are not connected beforehand.
  • 2 a b Output whether two nodes a, b (1 \le a, b \le N, a \neq b) are connected. Two nodes are connected if there is a path from the first node to the second.

There will be Q of these operations.

Input Specification

The first line will 2 integers, N, Q (1 \le N, Q \le 10^5).

The next Q lines will each contain a operation as defined above.

Output Specification

For each type 2 operation, print YES if the two nodes are connected, and NO otherwise. (Exact capitalization).


Subtask 1 [20%]

N, Q \le 100

Subtask 2 [80%]

No further constraints.

Sample Input

4 5
2 1 3
1 1 2
1 2 4
2 1 4
2 3 4

Sample Output



There are no comments at the moment.