H - Connected Components Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

N 頂点のグラフがあり、頂点には 1, \dots, N の番号が付けられています。はじめ、このグラフに辺は存在しません。

以下の形式のクエリを Q 個処理してください。

  • 1 u v : 頂点 u, v を結ぶ無向辺を追加する。
  • 2 u : クエリが与えられた時点でのグラフにおいて、頂点 u から 0 本以上の辺を通ってたどり着くことのできる頂点の番号を全て昇順に出力する。

ただし、1 つのテストケースにおいて、2 u の形式のクエリで出力する頂点の番号の個数の合計は 2 \times 10^5 個以下であることが保証されます。

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 u v の形式のクエリにおいて 1 \leq u \lt v \leq N
  • 2 u の形式のクエリにおいて 1 \leq u \leq N
  • 2 u の形式のクエリが 1 個以上存在する。
  • 1 つのテストケースにおいて、2 u の形式のクエリで出力する頂点の番号の個数の合計は 2 \times 10^5 個以下である。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。ただし、\mathrm{Query}_i \, (1 \leq i \leq Q) は i 番目に与えられるクエリを表す。

N Q
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

出力

2 u の形式のクエリそれぞれに対し、クエリが与えられた時点でのグラフにおいて、頂点 u から 0 本以上の辺を通ってたどり着くことのできる頂点の番号を全て昇順に出力せよ。 それぞれの頂点の番号は空白区切りで出力し、末尾には改行を出力すること。

入力例 1

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

出力例 1

1 2
5
1 2 3 4
1 2 3 4

入力例 2

1 2
2 1
2 1

出力例 2

1
1

入力例 3

3 3
1 1 2
2 1
1 1 2

出力例 3

1 2

同じ頂点の組を結ぶ辺が複数回追加されることもあります。

Score : 6 points

Problem Statement

There is a graph with N vertices, numbered 1, \dots, N. Initially, there is no edge in this graph.

Process Q queries of the format below.

  • 1 u v : Add an undirected edge connecting Vertex u and Vertex v.
  • 2 u: List in ascending order all indices of vertices reachable from Vertex u by traversing zero or more edges at the moment the query is given.

Here, it is guaranteed that the total number of vertices to be listed in queries of the form 2 u within a single test case is at most 2 \times 10^5.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq u \lt v \leq N in a query of the form 1 u v.
  • 1 \leq u \leq N in a query of the form 2 u.
  • There is at least one query of the form 2 u.
  • Within a single test case, the total number of vertices to be listed in queries of the form 2 u is at most 2 \times 10^5.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format, where \mathrm{Query}_i \, (1 \leq i \leq Q) represents the i-th query given:

N Q
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

Output

For each query of the format 2 u, print in ascending order all indices of vertices reachable from Vertex u by traversing zero or more edges at the moment the query is given. The indices should be separated by spaces and followed by a newline.

Sample Input 1

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

Sample Output 1

1 2
5
1 2 3 4
1 2 3 4

Sample Input 2

1 2
2 1
2 1

Sample Output 2

1
1

Sample Input 3

3 3
1 1 2
2 1
1 1 2

Sample Output 3

1 2

Multiple edges may be added between the same pair of vertices.