在烏托邦王國（Kingdom of Utopia），社會已經高度數位化，連人際關係也不例外。總督建立了一個由數十億個 GPU 組成的龐大資料庫系統，用以記錄居民的人際關係。對於任何兩位居民，若他們是熟人，則必須在王國的資料庫中註冊。請注意，註冊的關係是相互的：如果 $A$ 被註冊為 $B$ 的熟人，那麼 $B$ 也會被註冊為 $A$ 的熟人。

為了進一步全面數位化人際關係，Aurelius IV 國王提出了「數位情感點數」（numerical affectionate points）。烏托邦王國的每位居民都會獲得 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