Jesteś dziennikarzem gazety JOI i odpowiadasz za artykuły sportowe.

Do wczoraj w Chorwacji rozgrywano turniej ligowy systemem „każdy z każdym” z udziałem $n$ drużyn piłkarskich. Komitet organizacyjny zawodów najwyraźniej przyznał każdej drużynie miejsce od $1$. do $n$. na podstawie wyników meczów oraz regulaminu. Wraz z wynikami (zwycięstwo lub porażka) niektórych meczów przekazano Ci następujące informacje:

• Informacja $1$: Nie było żadnego meczu zakończonego remisem.
• Informacja $2$: Wszystkie drużyny zajęły różne miejsca.
• Informacja $3$: Dla wszystkich $1 \le a < b \le n$, w meczu pomiędzy drużyną z $a$-tego miejsca a drużyną z $b$-tego miejsca zawsze wygrywała drużyna z $a$-tego miejsca.

Aby napisać artykuł, postanowiłeś odtworzyć tabelę wyników na podstawie wyników niektórych meczów oraz przekazanych Informacji $1$–$3$.

Napisz program, który na podstawie podanych na wejściu wyników niektórych meczów wypisze $1$ tabelę wyników zgodną z przekazanymi informacjami. Ponadto rozstrzygnij, czy oprócz wypisanej tabeli wyników istnieje jakakolwiek inna tabela wyników zgodna z przekazanymi informacjami.

Tabela wyników oznacza tutaj listę drużyn uporządkowaną w kolejności od $1$. do $n$. miejsca.

Przykłady

Przykład 1 (Przypadek, gdy istnieje tylko $1$ tabela wyników zgodna z informacjami)

Załóżmy, że liczba drużyn wynosi $4$, drużyny są ponumerowane od $1$ do $4$, a wyniki meczów przedstawia poniższa tabela.

Gdy w wierszu $i$ i kolumnie $j$ znajduje się $\circ$, oznacza to, że w meczu między drużyną numer $i$ a drużyną numer $j$ wygrała drużyna numer $i$. Gdy znajduje się tam $\times$, oznacza to, że wygrała drużyna numer $j$. Znak $?$ oznacza, że wynik meczu nie został podany.

Wówczas istnieje tylko $1$ tabela wyników zgodna z przekazanymi informacjami:

• $1$. miejsce: drużyna numer $3$
• $2$. miejsce: drużyna numer $4$
• $3$. miejsce: drużyna numer $1$
• $4$. miejsce: drużyna numer $2$

Przykład 2 (Przypadek, gdy istnieje wiele tabel wyników zgodnych z informacjami)

Załóżmy, że liczba drużyn wynosi $3$, drużyny są ponumerowane od $1$ do $3$, a wyniki meczów przedstawia poniższa tabela.

Wówczas istnieją $2$ tabele wyników zgodne z przekazanymi informacjami:

• $1$. miejsce: drużyna numer $2$, $2$. miejsce: drużyna numer $1$, $3$. miejsce: drużyna numer $3$
• $1$. miejsce: drużyna numer $2$, $2$. miejsce: drużyna numer $3$, $3$. miejsce: drużyna numer $1$

Wejście

W $1$. wierszu zapisana jest liczba drużyn piłkarskich $n$. Każda drużyna ma przypisany numer od $1$ do $n$.

W $2$. wierszu zapisana jest liczba podanych wyników meczów $m$.

Wiersze od $3$. do $m + 2$ opisują wyniki meczów. Każdy wiersz zawiera $2$ oddzielone spacją liczby całkowite $i, j$ i oznacza, że drużyna numer $i$ pokonała drużynę numer $j$.

Liczby $n, m$ spełniają warunki $1 \le n \le 5000$, $1 \le m \le 100000$.

Wśród danych testowych używanych podczas oceniania $30\%$ spełnia warunki $1 \le n \le 7$, $1 \le m \le 15$. Ponadto $60\%$ spełnia warunki $1 \le n \le 100$, $1 \le m \le 2000$.

Wyjście

Wyjście składa się z $n + 1$ wierszy.

W $n$ wierszach od $1$. do $n$. wypisz tabelę wyników zgodną z przekazanymi informacjami. W $i$-tym wierszu ($1 \le i \le n$) wypisz numer drużyny, która zajęła $i$-te miejsce.

W wierszu $n + 1$ wypisz liczbę całkowitą określającą, czy oprócz wypisanej tabeli wyników istnieje inna tabela wyników zgodna z przekazanymi informacjami: jeśli nie istnieje, wypisz $0$, a jeśli istnieje, wypisz $1$.

Przykłady wejścia i wyjścia

Przykładowe wejście 1

Wejście i wyjście odpowiadające Przykładowi $1$ są następujące.

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

Przykładowe wyjście 1

3
4
1
2
0

Przykładowe wejście 2

Dane wejściowe odpowiadające Przykładowi $2$ są następujące.

3
2
2 1
2 3

Dla tych danych wejściowych możliwe są następujące $2$ warianty danych wyjściowych; można wypisać dowolny z nich.

Przykładowe wyjście 2

2
1
3
1

2
3
1
1