分数: 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
可以在同一对顶点之间添加多条边。