题目描述

给定一个包含 n 个顶点和 m 条边的无向图，要求以邻接矩阵和邻接表的形式输出该图。

输入格式

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

接下来的 m 行，每行输入两个以空格分隔的正整数 u 和 v，表示顶点 u 和顶点 v 之间有一条无向边直接相连。

输出格式

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

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

输入输出样例

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

输出

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