Hide

Problem D
Vinir

Languages en is
/problems/vinir/file/statement/en/img-0001.png
Image from Pixabay
Benni is quite fascinated with how many friends people have and one weekend when he was at a large get-together he decided to write down every friendship made. As everyone knows, friendship is transitive, that is to say, if Hannes and Bjarki are friends and Bjarki and Arnar are friends, then Hannes and Arnar are also friends. Can you help Benni figure out how many friends everyone has?

Input

The first line of the input contains two integers $N$, the number of people present, and $Q$, the number of queries. The next $Q$ lines contain one query each. There are two kinds of queries, 1 a b signifies that Benni saw $1 \leq a \leq n$ and $1 \leq b \leq n$ becoming friends. The other kind of query is of the form 2 a which means Benni wants to know how many friends $a$ has made.

Output

For each query of the type 2 a, print a single line denoting how many friends $a$ has made.

Scoring

Group

Points

Constraints

1

20

$1 \leq N,Q \leq 1000$

2

30

$1 \leq N,Q \leq 10^5$, all friendships made come before the queries asking for the number of friends.

3

50

$1 \leq N,Q \leq 10^5$

Sample Input 1 Sample Output 1
2 3
1 1 2
2 1
2 2
1
1
Sample Input 2 Sample Output 2
4 5
2 1
1 1 4
2 4
1 3 4
2 3
0
1
2

Please log in to submit a solution to this problem

Log in