← 返回题目列表

AtCoder · abc276_b

C. 邻接列表

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

分数: 200 点

问题陈述

有 N 城市编号 1, \dots, N,和 M 连接城市的道路。
的 i第路 (1 \leq i \leq M) 连接城市 A_i 和城市 B_i.

打印 N 行如下。

  • 让 d_i 是与城市直接相连的城市数量 i \, (1 \leq i \leq N),那些城市是 city a_{i, 1}, \dots, 城市 a_{i, d_i},在 升序.
  • 的 i第行 (1 \leq i \leq N) 应包含 问题陈述中指定的 d_i + 1 整数 d_i, a_{i, 1}, \dots, a_{i, d_i} 按此顺序,用空格分隔。

约束

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
\vdots
A_M B_M

输出

打印 N 行。


样本输入 1

6 6
3 6
1 3
5 6
2 5
1 2
1 6

示例输出 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

与城市直接相连的城市 1 是城市 2, 城市 3和城市 6。因此,我们有 d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6,所以你应该打印 3, 2, 3, 6 按此顺序位于第一行,以空格分隔。

请注意 a_{i, 1}, \dots, a_{i, d_i} 必须按升序排列。例如,打印是不可接受的 3, 3, 2, 6 在此顺序的第一行。


示例输入 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

示例输出 2

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