题目描述

有 $N$ 座城市，编号为 $1$ 到 $N$。城市之间共有 $M$ 条双向道路，每条道路连接两座不同的城市，同一对城市之间最多有一条道路。

请依次整理每座城市的直接邻居：先统计与它有道路直接相连的城市数量，再把这些城市的编号按从小到大的顺序列出来。这里的“直接相连”只看一条道路，不包括经过其他城市才能到达的情况。

输入格式

第一行输入两个整数 $N,M$，分别表示城市数和道路数。

接下来 $M$ 行，每行输入两个整数 $A_i,B_i$，表示城市 $A_i$ 与城市 $B_i$ 之间有一条双向道路。

输出格式

输出 $N$ 行，依次对应城市 $1,2,\ldots,N$。

第 $i$ 行先输出一个整数 $d_i$，表示与城市 $i$ 直接相连的城市数量；然后按编号从小到大的顺序，输出这 $d_i$ 座城市的编号。同行整数之间用空格分隔。

如果城市 $i$ 没有直接相连的城市，这一行只输出 0。

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

城市 1 直接连接城市 2、3、6，所以第一行输出 3 2 3 6。城市 4 没有连接任何道路，因此第四行只输出 0。

输入样例 #2

4 3
2 4
1 3
1 2

输出样例 #2

2 2 3
2 1 4
1 1
1 2

样例解释 #2

城市 1 的邻居是 2、3；城市 2 的邻居是 1、4。输入道路的先后顺序不影响输出，邻居编号必须按升序排列。

输入样例 #3

2 1
1 2

输出样例 #3

1 2
1 1

数据范围

$2 \le N \le 10^5$，$1 \le M \le 10^5$。

$1 \le A_i < B_i \le N$。不存在重复道路，所有输入均为整数。

题目来源

洛谷 AT_abc276_b；AtCoder 原题。中文表述按原题规则整理。