题目描述

在乌托邦王国，社会关系已经高度数字化。总督建立了一个巨大的数据库，用来记录居民之间的关系。任意两个居民如果是熟人，就必须在数据库中登记。注意，登记关系是相互的：如果 $A$ 被登记为 $B$ 的熟人，那么 $B$ 也被登记为 $A$ 的熟人。

在完全数字化人际关系的最后一步中，奥勒留四世国王提出了“数字好感点”的制度。每个居民都会得到 $10000$ 点好感点，并且必须把这些好感点分配给自己在数据库中登记过关系的其他居民。

例如，如果 $A$ 登记的熟人有 $B$ 和 $C$，那么 $A$ 可以给 $B$ 分配 $3000$ 点，给 $C$ 分配 $7000$ 点。如果 $A$ 没有和 $D$ 登记关系，那么 $A$ 不能给 $D$ 分配任何好感点。每次分配的好感点必须是整数，可以是从 $0$ 到 $10000$ 的任意整数。

国王希望分配方案公平且对等：如果 $A$ 给了 $B$ 恰好 $x$ 点好感点，那么 $B$ 也必须给 $A$ 恰好 $x$ 点好感点。此外，每个居民必须把自己所有的好感点都分配出去，也就是说每个居民分配给所有熟人的好感点之和必须为 $10000$。

现在给出登记关系数据库。请判断是否存在一种合法的好感点分配方案。如果存在，请输出任意一种合法方案。

输入格式

第一行包含两个整数 $n,m$，分别表示乌托邦居民数量和登记关系数量。居民编号为 $1$ 到 $n$。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示居民 $a$ 和居民 $b$ 之间有一条登记关系。

数据满足：

所有关系互不相同。如果输入中出现关系 $a\ b$，则表示 $a$ 与 $b$ 互为熟人，不会再出现反向关系 $b\ a$。

输出格式

如果存在合法分配方案，输出 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个数表示居民 $i$ 和居民 $j$ 之间相互分配的好感点数量。

输出矩阵需要满足：

• 对角线位置 $i=j$ 的值必须为 $0$；
• 如果 $i$ 和 $j$ 没有登记关系，则矩阵中对应值必须为 $0$；
• 如果 $i$ 和 $j$ 有登记关系，则对应值是一个 $0$ 到 $10000$ 之间的整数；
• 矩阵必须对称；
• 每一行的和必须等于 $10000$。

如果不存在合法分配方案，输出：

-1

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

输入 #2

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

输出 #2

-1