← 返回题目列表

AtCoder · past202203_h

H. 连接的组件

中文机器翻译题面 查看原题

分数: 6 点

问题陈述

有一个图表 N 顶点,编号 1, \dots, N。最初,该图中没有边。

流程 Q 以下格式的查询。

  • 1 u v : 添加连接顶点的无向边 u 和顶点 v.
  • 2 u:按升序列出从 Vertex 可到达的所有顶点索引 u 通过在给出查询时遍历零个或多个边。

这里,保证在表单的查询中列出的顶点总数 2 u 在单个测试用例中最多 2 \times 10^5.

约束

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq u \lt v \leq N 在表单的查询中 1 u v.
  • 1 \leq u \leq N 在表单的查询中 2 u.
  • 至少有一个以下形式的查询 2 u.
  • 在单个测试用例中,表单查询中列出的顶点总数 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,按升序打印从 Vertex 可到达的所有顶点索引 u 通过在给出查询时遍历零个或多个边。 索引应以空格分隔,后跟换行符。


示例输入 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

可以在同一对顶点之间添加多条边。