题目描述

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

输入格式

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

输出格式

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

样例

输入样例 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

4 2
1 2
3 4

输出样例 2

0 1 0 0 
1 0 0 0 
0 0 0 1 
0 0 1 0

输入样例 3

3 3
1 2
2 3
1 3

输出样例 3

0 1 1 
1 0 1 
1 1 0

输入样例 4

2 1
1 2

输出样例 4

0 1 
1 0