luogu#B3643. 图的存储

图的存储

题目描述

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

输入格式

第一行输入两个正整数 nnmm,表示图的顶点数和边数。

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

输出格式

首先输出 nnnn 列的矩阵,以空格隔开每一行之间的数表示邻接矩阵。第 ii 行第 jj 列的数为 11 则表示顶点 i,ji,j 之间有一条边直接相连;若为 00 则表示没有直接相连的边。

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

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

提示

样例的图如图所示:

数据保证,对于所有数据,1n10001 \leq n \leq 10001m1051 \leq m \leq 10^5,且图无重边无自环。