D - Play Train Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋君は電車のおもちゃを連結させたり分離させたりして遊んでいます。
電車は N 個あり、電車 1 、電車 2 、\ldots 、電車 N と名前がついています。
はじめ電車どうしは連結しておらず全てバラバラです。

クエリが Q 個与えられるので、与えられた順番に処理してください。
クエリは次の 3 種類のいずれかです。

  • 1 x y ：電車 x の後部と、電車 y の前部を連結させる。
    以下のことが保証されます。

    • x \neq y
    • クエリを処理する直前に、電車 x の後部と連結している電車は存在しない
    • クエリを処理する直前に、電車 y の前部と連結している電車は存在しない
    • クエリを処理する直前に、電車 x と電車 y は異なる連結成分に属する

  • 2 x y ：電車 x の後部と、電車 y の前部を分離させる。
    以下のことが保証されます。

    • x \neq y
    • クエリを処理する直前に、電車 x の後部と電車 y の前部は直接連結している

  • 3 x ：電車 x が含まれる連結成分に属する電車の番号を、先頭から順番に全て出力する。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq x \leq N
  • 1 \leq y \leq N
  • 入力は全て整数
  • クエリは全て問題文の条件を満たす
  • 3 x の形式のクエリで出力する電車の番号の個数の合計は 10^6 以下

入力

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

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

i 番目のクエリ \mathrm{query}_i では、まずクエリの種類 c_i（ 1, 2, 3 のいずれか）が与えられる。
c_i = 1,2 の場合は x,y が追加で与えられ、c_i =3 の場合は x が追加で与えられる。

すなわち、各クエリは以下に示す 3 つの形式のいずれかである。

1 x y

2 x y

3 x

出力

ある c_i = 3 のタイプのクエリにおいて、出力すべき値が j_1, j_2, \ldots , j_M であるとする。
このとき以下の形式で 1 行に出力せよ。

M j_1 j_2 \ldots j_M

c_i = 3 のタイプのクエリの数を q として、q 行出力せよ。
k (1 \leq k \leq q) 行目では k 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

7 14
1 6 3
1 4 1
1 5 2
1 2 7
1 3 5
3 2
3 4
3 6
2 3 5
2 4 1
1 1 5
3 2
3 4
3 6

出力例 1

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

\mathrm{query}_5 まで処理した時、電車は以下のようになっています。
この時、たとえば電車 2 は、電車 3,5,6,7 と同じ連結成分に属していますが、電車 1,4 とは同じ連結成分に属していません。

\mathrm{query}_{11} まで処理した時、電車は以下のようになっています。

Score : 400 points

Problem Statement

Takahashi is playing with toy trains, connecting and disconnecting them.
There are N toy train cars, with car numbers: Car 1, Car 2, \ldots, Car N.
Initially, all cars are separated.

You will be given Q queries. Process them in the order they are given. There are three kinds of queries, as follows.

  • 1 x y: Connect the front of Car y to the rear of Car x.
    It is guaranteed that:

    • x \neq y
    • just before this query, no train is connected to the rear of Car x;
    • just before this query, no train is connected to the front of Car y;
    • just before this query, Car x and Car y belong to different connected components.

  • 2 x y: Disconnect the front of Car y from the rear of Car x.
    It is guaranteed that:

    • x \neq y;
    • just before this query, the front of Car y is directly connected to the rear of Car x.

  • 3 x: Print the car numbers of the cars belonging to the connected component containing Car x, from front to back.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq x \leq N
  • 1 \leq y \leq N
  • All values in input are integers.
  • All queries satisfy the conditions in the Problem Statement.
  • The queries of the format 3 x ask to print at most 10^6 car numbers in total.

Input

Input is given from Standard Input in the following format:

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

The i-th query \mathrm{query}_i begins with an integer c_i (1, 2, or 3) representing the kind of the query, followed by x and y if c_i = 1 or 2, and followed by x if c_i = 3.

In short, each query is in one of the following three formats:

1 x y

2 x y

3 x

Output

If a query with c_i = 3 asks to print the values j_1, j_2, \ldots, j_M, output the following line:

M j_1 j_2 \ldots j_M

Your output should consist of q lines, where q is the number of queries with c_i = 3.
The k-th line (1 \leq k \leq q) should contain the response to the k-th such query.

Sample Input 1

7 14
1 6 3
1 4 1
1 5 2
1 2 7
1 3 5
3 2
3 4
3 6
2 3 5
2 4 1
1 1 5
3 2
3 4
3 6

Sample Output 1

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

The figure below shows the cars when the first 5 queries are processed.
For example, Car 2 belongs to the same connected component as Cars 3, 5, 6, 7, which is different from the connected component containing Cars 1, 4.

The figure below shows the cars when the first 11 queries are processed.