在乌托邦王国，社会已经高度数字化，连人际关系也不例外。总督建立了一个拥有数十亿个 GPU 的庞大数据库系统，用于记录居民的人际关系。对于任意两名居民，如果他们是熟人，则必须在王国的数据库中进行登记。注意，登记的关系是相互的：如果 $A$ 被登记为 $B$ 的熟人，那么 $B$ 也被登记为 $A$ 的熟人。

为了全面实现人际关系的数字化，奥雷利乌斯四世国王（King Aurelius IV）提出了“数字情感点数”。乌托邦王国的每位居民都会获得 10,000 点情感点数。居民需要将他们的情感点数分配给在数据库中登记过关系的其他人。例如，如果 $A$ 登记为 $B$ 和 $C$ 的熟人，则 $A$ 可以分配 3,000 点情感点数给 $B$，并分配 7,000 点情感点数给 $C$。如果 $A$ 与 $D$ 没有登记关系，则 $A$ 不能给 $D$ 任何情感点数。居民可以分配 0 到 10,000 之间的任意整数数量的情感点数。

国王希望确保点数分配是公平且对等的：如果 $A$ 给 $B$ 分配了 $x$ 点情感点数，那么 $B$ 也必须给 $A$ 同样的 $x$ 点情感点数。此外，居民必须分配出他们所有的情感点数；即一名居民分配给其所有熟人的情感点数之和必须为 10,000。

国王将登记的关系数据库交给你，他希望你判断王国是否能够实施这一协议。你必须确定国王的方案是否可行，如果可行，你必须给出一个有效的点数分配方案。

输入格式

输入的第一行包含两个整数 $n$ ($2 \le n \le 1,000$) 和 $m$ ($1 \le m \le 5,000$)，其中 $n$ 是乌托邦的公民人数，$m$ 是登记的关系数量。公民编号从 1 到 $n$。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，描述公民 $a$ 和 $b$ 之间的一段登记关系。所有关系都是唯一的。如果输入中出现了 $a \ b$，则表示 $a$ 是 $b$ 的熟人，$b$ 也是 $a$ 的熟人，因此输入中不会再出现 $b \ a$。

输出格式

如果能够按照国王的要求分配情感点数，则输出 $n$ 行，每行包含 $n$ 个整数。位于 $(i, j)$ 位置的数字表示公民 $i$ 和 $j$ 之间的情感点数。注意，在对角线 $i = j$ 的位置，情感点数显然为 0。

如果无法按照国王的要求分配情感点数，则直接输出 $-1$。

样例

样例输入 1

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

样例输出 1

0 7500 2500 0 0
7500 0 2500 0 0
2500 2500 0 2500 2500
0 0 2500 0 7500
0 0 2500 7500 0

样例输入 2

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

样例输出 2

-1