图的存储

题目描述

给定一个 $n$ 个顶点 $m$ 条边的无向图。请以邻接矩阵和邻接表的形式输出这一张图。

输入格式

第一行输入两个正整数 $n$ 和 $m$，表示图的顶点数和边数。

第二行开始，往后 $m$ 行，每行输入两个以空格隔开的正整数 $u,v$，表示 $u,v$ 顶点之间有一条边直接相连。

输出格式

首先输出 $n$ 行 $n$ 列的矩阵，以空格隔开每一行之间的数表示邻接矩阵。第 $i$ 行第 $j$ 列的数为 $1$ 则表示顶点 $i,j$ 之间有一条边直接相连；若为 $0$ 则表示没有直接相连的边。

再往后输出 $n$ 行。第 $i$ 行首先先输出一个整数 $d_i$，表示这个顶点的度数，再按照从小到大的顺序，依次输出与顶点 $i$ 直接相连的所有顶点。

输入样例 #1

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

输出样例 #1

0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
2 2 3
2 1 3
4 1 2 4 5
1 3
1 3

输入样例 #2

5 7
1 5
3 4
1 3
2 4
3 5
2 3
1 4

输出样例 #2

0 0 1 1 1
0 0 1 1 0
1 1 0 1 1
1 1 1 0 0
1 0 1 0 0
3 3 4 5
2 3 4
4 1 2 4 5
3 1 2 3
2 1 3

输入样例 #3

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

输出样例 #3

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

数据范围

数据保证，对于所有数据，$1 \leq n \leq 1000$，$1 \leq m \leq 10^5$，且图无重边无自环。