图的存储

题目描述

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

输入格式

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

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

输出格式

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

再往后输出 \(n\) 行(邻接表)。第 \(i\) 行 按照从小到大的顺序，依次输出与顶点 \(i\) 直接相连的所有顶点。

输入输出样例 #1

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

说明/提示

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