Adjacency List

题目描述

有 $N$ 个城市，编号为 $1, \dots, N$，以及连接城市的 $M$ 条道路。
第 $i$ 条道路 $(1 \leq i \leq M)$ 连接城市 $A_i$ 和城市 $B_i$。 输出 $N$ 行，格式如下。

设 $d_i$ 为与城市 $i$ 直接相连的城市数目 $(1 \leq i \leq N)$，这些城市为城市 $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}$，按此顺序并以空格分隔。

输入格式

输入按如下格式从标准输入给出： $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

按问题陈述中指定的格式输出 $N$ 行。

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

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

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

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

提示

$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)$. 输入中的所有数值均为整数。与城市 $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$ 是不被接受的。

标签: AtCoder|abc276B

来源

AtCoder|abc276B