You are a reporter for the JOI Newspaper, in charge of sports articles.

By yesterday, a round-robin league tournament among $n$ soccer teams had been held in Croatia. The tournament organizing committee apparently assigned each team a rank from $1$-st place to $n$-th place based on the match results and the regulations. Along with the win/loss results of some of the matches, the following information was conveyed to you:

• Information $1$: There were no tied matches.
• Information $2$: Every team was assigned a distinct rank.
• Information $3$: For all $1 \le a < b \le n$, in the match between the $a$-th place team and the $b$-th place team, the $a$-th place team always won.

To write your article, you decided to infer the standings table based on the win/loss results of some of the matches and Information $1$–$3$ conveyed to you.

Write a program that, given the win/loss results of some of the matches as input, outputs $1$ standings table consistent with the conveyed information. Also, determine whether there exists any standings table consistent with the conveyed information other than the output standings table.

Here, the standings table refers to the list of teams ordered from $1$-st place to $n$-th place.

Examples

Example 1 (When there is only $1$ standings table consistent with the information)

Suppose the number of teams is $4$, the teams are numbered from $1$ to $4$, and the win/loss results are given by the following table.

When row $i$, column $j$ is $\circ$, it means that in the match between team $i$ and team $j$, team $i$ won. When it is $\times$, it means that team $j$ won. $?$ means that the win/loss result is not given.

In this case, there is only $1$ standings table consistent with the conveyed information, as follows:

• $1$-st place: Team $3$
• $2$-nd place: Team $4$
• $3$-rd place: Team $1$
• $4$-th place: Team $2$

Example 2 (When there are multiple standings tables consistent with the information)

Suppose the number of teams is $3$, the teams are numbered from $1$ to $3$, and the win/loss results are given by the following table.

In this case, there are $2$ standings tables consistent with the conveyed information, as follows:

• $1$-st place: Team $2$, $2$-nd place: Team $1$, $3$-rd place: Team $3$
• $1$-st place: Team $2$, $2$-nd place: Team $3$, $3$-rd place: Team $1$

Input

The $1$-st line contains the number of soccer teams $n$. Each team is numbered from $1$ to $n$.

The $2$-nd line contains the number of given match results $m$.

From the $3$-rd line to the $m + 2$-th line, the match results are given. Each line contains $2$ integers $i, j$ separated by a space, representing that team $i$ won against team $j$.

$n, m$ satisfy $1 \le n \le 5000$, $1 \le m \le 100000$.

Among the test data used for grading, $30\%$ of the total score satisfies $1 \le n \le 7$, $1 \le m \le 15$. Furthermore, $60\%$ of the total score satisfies $1 \le n \le 100$, $1 \le m \le 2000$.

Output

The output consists of $n + 1$ lines.

In the $n$ lines from the $1$-st line to the $n$-th line, output a standings table consistent with the conveyed information. On the $i$-th line ($1 \le i \le n$), output the team number of the $i$-th place team.

On the $n + 1$-th line, output an integer indicating whether there exists any standings table consistent with the conveyed information other than the output standings table: output $0$ if none exists, and output $1$ if one exists.

Sample Input and Output

Sample Input 1

The input and output corresponding to Example $1$ are as follows.

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

Sample Output 1

3
4
1
2
0

Sample Input 2

The input data corresponding to Example $2$ is as follows.

3
2
2 1
2 3

For this input data, the following $2$ output data are possible; outputting either of them is accepted.

Sample Output 2

2
1
3
1

2
3
1
1