D - Pigeon Swap Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

鳩 1, 鳩 2,\ldots, 鳩 N の N 羽の鳩と、巣 1, 巣 2,\ldots, 巣 N の N 個の巣があります。

はじめ、鳩 i (1\leq i\leq N) は巣 i にいます。

鳩たちに対して Q 回の操作を行います。

操作は次の 3 種類のうちのいずれかです。

  • 種類 1 : 整数 a,b (1\leq a\leq N,1\leq b\leq N) が与えられる。鳩 a を今いる巣から取り出し、巣 b へ移動する。
  • 種類 2 : 整数 a,b (1\leq a\lt b\leq N) が与えられる。巣 a にいる鳩をすべて巣 b へ移動し、巣 b にいる鳩をすべて巣 a へ移動する。これら 2 つの移動は一斉に行われる。
  • 種類 3 : 整数 a (1\leq a\leq N) が与えられる。鳩 a が今いる巣の番号を報告する。

Q 回の操作を順に行ったときの、種類 3 の各操作における報告の結果を出力してください。

制約

  • 1\leq N\leq10 ^ 6
  • 1\leq Q\leq3\times10 ^ 5
  • 入力される操作はすべて種類 1, 種類 2, 種類 3 のいずれかである。
  • 入力される操作は問題文中の制約を満たす。
  • 入力される操作のうちに種類 3 の操作が 1 つ以上含まれる。
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
op _ 1
op _ 2
\vdots
op _ Q

ただし、i+1 行目の入力 op _ i は i 番目の操作を表しており、op _ i は次のいずれかの形式である。

i 番目の操作が種類 1 の操作のとき、i+1 行目は次の形式で与えられる。

1 a b

これは、与えられる整数を a と b として種類 1 の操作を行うことを表している。

i 番目の操作が種類 2 の操作のとき、i+1 行目は次の形式で与えられる。

2 a b

これは、与えられる整数を a と b として種類 2 の操作を行うことを表している。

i 番目の操作が種類 3 の操作のとき、i+1 行目は次の形式で与えられる。

3 a

これは、与えられる整数を a として種類 3 の操作を行うことを表している。

出力

与えられる種類 3 の操作の個数を q 個として、q 行にわたって出力せよ。

i 行目 (1\leq i\leq q) には、種類 3 の操作のうち i 番目の操作で報告される巣の番号を出力せよ。

入力例 1

6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2

出力例 1

4
5
2
5

与えられる操作で、鳩は以下の図のように移動します。

種類 3 の操作でそれぞれ報告すべき巣の番号は 4,5,2,5 なので、4 5 2 5 を 4 行にわたって出力してください。

入力例 2

1 2
1 1 1
3 1

出力例 2

1

種類 1 の操作で、鳩を取り出した巣にそのまま戻す場合もあります。

入力例 3

30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8

出力例 3

3
15
7

Score : 350 points

Problem Statement

There are N pigeons labeled 1, 2, \ldots, N and N nests labeled 1, 2, \ldots, N.

Initially, pigeon i (1 \leq i \leq N) is in nest i.

You will perform Q operations on these pigeons.

There are three types of operations:

  • Type 1: You are given integers a and b (1 \leq a \leq N, 1 \leq b \leq N). Take pigeon a out of its current nest and move it to nest b.
  • Type 2: You are given integers a and b (1 \leq a < b \leq N). Move all pigeons in nest a to nest b, and move all pigeons in nest b to nest a. These two moves happen simultaneously.
  • Type 3: You are given an integer a (1 \leq a \leq N). Pigeon a reports the label of the nest it is currently in.

Print the result of each Type 3 operation in the order the operations are given.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq Q \leq 3 \times 10^5
  • Every operation is of Type 1, 2, or 3.
  • All operations are valid according to the problem statement.
  • There is at least one Type 3 operation.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
op _ 1
op _ 2
\vdots
op _ Q

Here, op _ i on the line i+1 represents the i-th operation in one of the following formats.

If the i-th operation is of Type 1, op _ i is in the following format:

1 a b

This corresponds to a Type 1 operation with the given integers being a and b.

If the i-th operation is of Type 2, op _ i is in the following format:

2 a b

This corresponds to a Type 2 operation with the given integers being a and b.

If the i-th operation is of Type 3, op _ i is in the following format:

3 a

This corresponds to a Type 3 operation with the given integer being a.

Output

Let the number of Type 3 operations be q. Print q lines. The i-th line (1 \leq i \leq q) should contain the nest number reported in the i-th Type 3 operation.

Sample Input 1

6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2

Sample Output 1

4
5
2
5

In the operations given, the pigeons move as shown in the figure below:

The nest numbers to be reported for the Type 3 operations are 4,5,2,5. Print 4, 5, 2, 5 on separate lines.

Sample Input 2

1 2
1 1 1
3 1

Sample Output 2

1

The destination nest of a Type 1 operation may be the same as the nest the pigeon is currently in.

Sample Input 3

30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8

Sample Output 3

3
15
7