You need to maintain $m$ sets, numbered $1, \dots, m$, which are initially empty.

There are $m$ operations in total:

1. Given $x, y$, insert $y$ into the set numbered $x$. It is guaranteed that $y$ was not previously in this set.
2. Given $x_1, x_2$, find the number of elements in the union of the sets numbered $x_1$ and $x_2$.

Input

The first line contains an integer $m$.

The next $m$ lines each contain three integers $1, x, y$ or $2, x_1, x_2$, representing an operation.

Output

For each operation of type $2$, output one line containing the answer.

Examples

Input 1

10
1 1 2
1 1 1
2 1 3
1 1 3
1 1 8
2 2 1
2 2 1
2 1 1
1 1 4
1 2 2

Output 1

2
4
4
4

Note

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, $1 \le m \le 10^6$ and $1 \le x, y, x_1, x_2 \le m$.

For $25\%$ of the data, $m \le 10^3$.

For another $25\%$ of the data, it is guaranteed that there are no type $1$ operations after the first type $2$ operation.

For another $25\%$ of the data, $m \le 2 \times 10^5$.

For the remaining $25\%$ of the data, there are no special restrictions.