ユートピア王国では、社会が高度にデジタル化されており、人間関係も例外ではありません。知事は、住民の人間関係を記録するために、数十億個のGPUからなる巨大なデータベースシステムを構築しました。任意の2人の住民の間で、もし彼らが知り合いであるならば、王国データベースに登録されている必要があります。登録された人間関係は相互的なものであることに注意してください。つまり、AがBの知り合いとして登録されているならば、BもAの知り合いとして登録されています。

人間関係を完全にデジタル化するための最後の取り組みとして、アウレリウス4世王は「数値的愛情ポイント」を提案しました。ユートピア王国のすべての住民には、10,000の愛情ポイントが与えられます。住民は、データベースに人間関係が登録されている他の住民に対して、自分の愛情ポイントを分配することが求められます。例えば、AがBおよびCの知り合いとして登録されている場合、AはBに3,000愛情ポイント、Cに7,000愛情ポイントを分配することができます。AがDと登録されていない場合、AはDに愛情ポイントを与えることはできません。住民は、0から10,000までの任意の整数値の愛情ポイントを分配できます。

王は、ポイントの分配が公平かつ平等であることを望んでいます。すなわち、AがBに $x$ 愛情ポイントを与えるならば、BもAに同じ $x$ 愛情ポイントを与えなければなりません。さらに、住民は自分の愛情ポイントをすべて分配しなければなりません。つまり、ある住民が知り合いに分配する愛情ポイントの合計は、必ず10,000にならなければなりません。

王はあなたに登録された人間関係のデータベースを提供し、王国がこのプロトコルを実装することが可能かどうかを判断することを求めています。王の計画が可能かどうかを判定し、可能であれば、有効な愛情ポイントの分配を王に提示してください。

入力

入力の最初の行には、2つの整数 $n$ ($2 \le n \le 1,000$) と $m$ ($1 \le m \le 5,000$) が含まれます。ここで $n$ はユートピアの市民の数、$m$ は登録された人間関係の数です。市民には1から $n$ までの番号が付けられています。

続く $m$ 行の各行には、2つの整数 $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