图的存储

题目描述

给定一个 $n$ 个顶点 $m$ 条边的无向图，结点编号从 $1$ 至 $n$。请以邻接矩阵的形式输出这一张图。

输入格式

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

第二行开始，往后 $m$ 行，每行输入两个以空格隔开的正整数 $u,v$，表示 $u,v$ 顶点之间有一条边直接相连（$u$、$v$ 是顶点编号，数值范围是 $1 \sim n$）。数据保证输入的图无重边。

输出格式

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

样例

输入

3 3
1 2
2 3
1 3

输出

0 1 1
1 0 1
1 1 0

数据范围

• $1 \le n \le 1000$
• $1 \le m \le 10^5$
• $1 \le u, v \le n$
• 数据保证图中无重边（即不会出现两条相同的边），但可能出现 $u = v$ 的自环，此时矩阵中对应位置记为 $1$。

提示：无向图的邻接矩阵是对称矩阵，且当输入数据规模较大时请注意使用较快的输出方式。