В Королевстве Утопия общество стало высокоцифровым, даже в отношениях. Правитель построил массивную систему баз данных из миллиардов GPU для записи отношений своих жителей. Между любыми двумя жителями требуется, чтобы, если они являются знакомыми, они были зарегистрированы в базе данных королевства. Заметьте, что зарегистрированные отношения являются взаимными: если $A$ зарегистрирован как знакомый $B$, то $B$ также зарегистрирован как знакомый $A$.

В последней попытке полностью оцифровать отношения король Аврелий 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

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

-1