Score : $200$ points

问题描述

有 $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}$ 的顺序排列，并用空格隔开。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ cities numbered $1, \dots, N$, and $M$ roads connecting cities.
The $i$-th road $(1 \leq i \leq M)$ connects city $A_i$ and city $B_i$.

Print $N$ lines as follows.

• Let $d_i$ be the number of cities directly connected to city $i \, (1 \leq i \leq N)$, and those cities be city $a_{i, 1}$, $\dots$, city $a_{i, d_i}$, in ascending order.
• The $i$-th line $(1 \leq i \leq N)$ should contain $d_i + 1$ integers $d_i, a_{i, 1}, \dots, a_{i, d_i}$ in this order, separated by spaces.

Constraints

• $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)$.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

Output

Print $N$ lines as specified in the Problem Statement.

Sample Input 1

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

Sample Output 1

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

The cities directly connected to city $1$ are city $2$, city $3$, and city $6$. Thus, we have $d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6$, so you should print $3, 2, 3, 6$ in the first line in this order, separated by spaces.

Note that $a_{i, 1}, \dots, a_{i, d_i}$ must be in ascending order. For instance, it is unacceptable to print $3, 3, 2, 6$ in the first line in this order.

Sample Input 2

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

Sample Output 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

update @ 2024/3/10 11:36:45