W Królestwie Utopii społeczeństwo stało się wysoce zdigitalizowane, nawet w relacjach międzyludzkich. Gubernator zbudował ogromny system bazodanowy oparty na miliardach procesorów graficznych (GPU), aby rejestrować relacje mieszkańców. Wymagane jest, aby każda znajomość między dwoma mieszkańcami była zarejestrowana w bazie danych królestwa. Zauważ, że zarejestrowana relacja jest obustronna: jeśli $A$ jest zarejestrowany jako znajomy $B$, to $B$ jest również zarejestrowany jako znajomy $A$.

W ramach ostatniego wysiłku na rzecz pełnej cyfryzacji relacji, król Aureliusz IV proponuje „numeryczne punkty sympatii”. Każdy mieszkaniec Królestwa Utopii otrzymuje 10 000 punktów sympatii. Mieszkańcy są następnie zobowiązani do rozdzielenia swoich punktów sympatii pomiędzy innych mieszkańców, z którymi mają zarejestrowaną relację w bazie danych. Na przykład, jeśli $A$ ma zarejestrowaną znajomość z $B$ oraz $C$, $A$ może przekazać 3 000 punktów sympatii dla $B$ oraz 7 000 punktów sympatii dla $C$. Jeśli $A$ nie ma zarejestrowanej znajomości z $D$, $A$ nie może przekazać $D$ żadnych punktów sympatii. Mieszkańcy mogą przekazać dowolną całkowitą liczbę punktów sympatii, od 0 do 10 000 włącznie.

Król chce mieć pewność, że podział punktów będzie sprawiedliwy i równy: jeśli $A$ przekazuje $B$ $x$ punktów sympatii, to $B$ musi również przekazać $A$ dokładnie $x$ punktów sympatii. Ponadto mieszkaniec musi rozdzielić wszystkie swoje punkty sympatii; suma wszystkich punktów sympatii, które mieszkaniec przekazuje swoim znajomym, musi wynosić 10 000.

Król przekazuje Ci bazę danych zarejestrowanych relacji i chce, abyś ustalił, czy wdrożenie tego protokołu przez Królestwo jest możliwe. Musisz określić, czy plan króla jest wykonalny, a jeśli tak, musisz przedstawić królowi poprawny rozkład punktów sympatii.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ ($2 \le n \le 1\,000$) oraz $m$ ($1 \le m \le 5\,000$), gdzie $n$ to liczba obywateli Utopii, a $m$ to liczba zarejestrowanych relacji. Obywatele są ponumerowani od 1 do $n$.

Każda z kolejnych $m$ linii zawiera dwie liczby całkowite $a$ oraz $b$ ($1 \le a, b \le n, a \neq b$), opisujące zarejestrowaną relację między obywatelami $a$ oraz $b$. Wszystkie relacje są unikalne. Jeśli $a$ $b$ pojawia się na wejściu, oznacza to, że $a$ jest znajomym $b$, a $b$ jest znajomym $a$, więc $b$ $a$ nie pojawi się na wejściu.

Wyjście

Jeśli podział punktów sympatii zgodnie z wymaganiami króla jest możliwy, wypisz $n$ linii, z których każda zawiera $n$ liczb całkowitych. Liczba na pozycji $(i, j)$ to liczba punktów sympatii między obywatelami $i$ oraz $j$. Zauważ, że na przekątnej, gdzie $i = j$, liczba punktów sympatii wynosi oczywiście 0.

Jeśli podział punktów sympatii zgodnie z wymaganiami króla nie jest możliwy, wypisz po prostu $-1$.

Przykład

Wejście 1

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

Wyjście 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

Wejście 2

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

Wyjście 2

-1