102761: [AtCoder]ABC276 B - Adjacency List

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

问题描述

有编号为$1, \dots, N$的$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}$，按此顺序用空格分隔。

约束

• $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)$
• 若$(i \neq j)$，则$(A_i, B_i) \neq (A_j, B_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