AT_abc276_b [ABC276B] Adjacency List

题目描述

有 $N$ 个城市，编号为 $1,\dots,N$，以及 $M$ 条连接城市之间的道路。
第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$。

请按照以下要求输出 $N$ 行内容。

• 设与城市 $i$ 直接相连的城市有 $d_i$ 个，记为 $a_{i,1},\dots,a_{i,d_i}$，并按升序排列。
• 第 $i$ 行请输出 $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$ 行内容。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

说明/提示

数据范围

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i < B_i \leq N\ (1 \leq i \leq M)$
• 如果 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$
• 所有输入的值均为整数

样例解释 1

与城市 $1$ 直接相连的城市是 $2, 3, 6$。因此，$d_1 = 3, a_{1,1} = 2, a_{1,2} = 3, a_{1,3} = 6$，所以第 $1$ 行应输出 $3, 2, 3, 6$，用空格分隔。注意，$a_{i,1},\dots,a_{i,d_i}$ 必须按升序排列。例如，如果第 $1$ 行输出 $3, 3, 2, 6$，则判为不正确。

由 ChatGPT 4.1 翻译