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

Problem DVinir

Input

Output

Scoring

Problem D
Vinir