F - Circle of Friends Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君のクラスには N 人の生徒がおり、それぞれ出席番号 1 から N が付けられています。新学期が始まり、クラスの親睦を深めるために、生徒たちはグループを作っていきます。

最初、すべての生徒はそれぞれ 1 人だけのグループに属しています（つまり N 個のグループがあります）。

先生が Q 回のクエリを出します。各クエリは次の 2 種類のいずれかです。

  • 種類 1 : 1 a b — 生徒 a が属するグループと生徒 b が属するグループを 1 つに合併する。合併後のグループには、元の両グループに属していた生徒が全員含まれる。すでに生徒 a と生徒 b が同じグループに属している場合（a = b の場合を含む）は何もしない。
  • 種類 2 : 2 x — 生徒 x が属するグループに含まれる生徒の人数を出力する。

すべての種類 2 のクエリに対して、与えられた順に答えを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 種類 1 のクエリにおいて、1 \leq a, b \leq N（a = b の場合もありうる）
  • 種類 2 のクエリにおいて、1 \leq x \leq N
  • 種類 2 のクエリは 1 つ以上存在する
  • 入力はすべて整数である

入力

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • 1 行目には、生徒の人数を表す整数 N と、クエリの回数を表す整数 Q が、スペース区切りで与えられる。
  • 続く Q 行にわたって、各クエリが 1 行ずつ与えられる。
  • クエリが種類 1 の場合は 1 a b の形式で、3 つの整数がスペース区切りで与えられる。ここで a, b は合併対象となる生徒の出席番号である。
  • クエリが種類 2 の場合は 2 x の形式で、2 つの整数がスペース区切りで与えられる。ここで x はグループの人数を調べたい生徒の出席番号である。

出力

種類 2 のクエリが与えられるたびに、生徒 x が属するグループに含まれる生徒の人数を 1 行に出力せよ。すべての答えはクエリが与えられた順に出力すること。

入力例 1

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

出力例 1

1
2
2
4

入力例 2

8 12
1 1 2
1 3 4
1 5 6
2 1
2 3
2 7
1 1 3
2 1
1 7 8
1 5 7
2 6
2 8

出力例 2

2
2
1
4
4
4

入力例 3

10 15
1 1 2
1 3 4
1 5 6
1 7 8
1 9 10
2 1
1 1 3
1 5 7
2 3
2 8
1 1 5
2 1
1 9 1
2 10
2 6

出力例 3

2
4
4
8
10
10

Score : 366 pts

Problem Statement

There are N students in Takahashi's class, each assigned a student number from 1 to N. As the new semester begins, the students form groups to deepen their friendships within the class.

Initially, every student belongs to a group containing only themselves (that is, there are N groups).

The teacher gives Q queries. Each query is one of the following two types:

  • Type 1: 1 a b — Merge the group that student a belongs to and the group that student b belongs to into a single group. The merged group contains all students who belonged to either of the original two groups. If student a and student b already belong to the same group (including the case where a = b), do nothing.
  • Type 2: 2 x — Output the number of students in the group that student x belongs to.

For all type 2 queries, output the answers in the order they are given.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • In type 1 queries, 1 \leq a, b \leq N (the case a = b is possible)
  • In type 2 queries, 1 \leq x \leq N
  • There is at least one type 2 query
  • All input values are integers

Input

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • The first line contains an integer N representing the number of students and an integer Q representing the number of queries, separated by a space.
  • The following Q lines each contain one query.
  • If the query is type 1, it is given in the format 1 a b, with three integers separated by spaces. Here, a and b are the student numbers of the students whose groups are to be merged.
  • If the query is type 2, it is given in the format 2 x, with two integers separated by a space. Here, x is the student number of the student whose group size is to be queried.

Output

Each time a type 2 query is given, output the number of students in the group that student x belongs to on a single line. All answers should be output in the order the queries are given.

Sample Input 1

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

Sample Output 1

1
2
2
4

Sample Input 2

8 12
1 1 2
1 3 4
1 5 6
2 1
2 3
2 7
1 1 3
2 1
1 7 8
1 5 7
2 6
2 8

Sample Output 2

2
2
1
4
4
4

Sample Input 3

10 15
1 1 2
1 3 4
1 5 6
1 7 8
1 9 10
2 1
1 1 3
1 5 7
2 3
2 8
1 1 5
2 1
1 9 1
2 10
2 6

Sample Output 3

2
4
4
8
10
10