Component sum - MarisaOJ: Marisa Online Judge

Given a graph of

$n$ vertices and no edge. There are

$q$ queries of either form: -

$1 u v$ add an edge between

$u$ and

$v$ . -

$2 u$ calculate the sum of the vertices in the connected component to which

$u$ belongs. ### Input - The first line contains 2 integers

$n, q$ . - The next

$q$ lines, each line is a query. For the

$1$ query, the line contains 3 integers

$1, u, v$ , and for the

$2$ query, the line contains 2 integers

$2, u$ . ### Output - For each query of type

$2$ , print on one line a single integer that is the sum of the vertices in the component to which

$u$ belongs. ### Constraints -

$1 \le n, q \le 10^5$ . -

$1 \le u, v \le n$ . ### Example Input:

$6 5 1 1 2 1 1 3 2 2 1 5 6 2 4$

Output:

$6 4$

Topic

DSU

Rating

1000

Solution (0)

Solution