Problem Name: The Worst Sportswriter
Problem
Problem Description: You are a reporter for the JOI Newspaper and in charge of sports articles. Until yesterday, a round-robin league tournament was held in Croatia by n soccer teams. According to the tournament organizing committee, each team was ranked from 1st to nth place based on the match results and regulations. With some match results, you were informed of the following information.
Information 1:
There were no tied games.
Information 2:
Each team received a different ranking.
Information 3:
For all 1 ≤ a < b ≤ n, the a-th team won the match against the b-th team.
To create an article, you decided to infer the ranking table based on the match results and the information provided. Create a program that outputs one ranking table that fits the given information when some match results are given. Also, determine whether there is a ranking table that fits the given information other than the output ranking table.
Here, the ranking table refers to a list of teams in order from 1st to nth place.
Example
Example 1 (when there is only one ranking table that fits the information)
Suppose there are 4 teams and each team is assigned a number from 1 to 4. The win-loss record is given in the table below.
If a square in the i-th row and j-th column is a circle, it means that team i won against team j. If it is a cross, it means that team j won against team i. "?" means that the match result is not given. In this case, there is only one ranking table that fits the given information, as follows.
1st Team 3
2nd Team 4
3rd Team 1
4th Team 2
Example 2 (when there are multiple ranking tables that fit the information)
Suppose there are 3 teams and each team is assigned a number from 1 to 3. The win-loss record is given in the table below.
In this case, there are two ranking tables that fit the given information, as follows.
1st Team 2
2nd Team 1
3rd Team 3
1st Team 2
2nd Team 3
3rd Team 1
Input
The input is given in the following format.
The first line contains the number of soccer teams, n.
The second line contains the number of win-loss records m.
From the third line to the m+2-th line, the win-loss records are given. Each line contains two integers i and j separated by a space, indicating that team i won against team j.
Constraints: 1 ≤ n ≤ 5000, 1 ≤ m ≤ 100000.
The test data used for grading has n ≤ 7 and m ≤ 15 for 30% of the cases, and n ≤ 100 and m ≤ 2000 for 60% of the cases.
Output
The output consists of n+1 lines.
For each of the n lines from the first line to the n-th line, output the ranking table that fits the given information.
Output the number of an integer that represents whether there exists a ranking table that fits the given information other than the output ranking table, on the n+1-th line. If there is no other ranking table, output 0. If there is another ranking table, output 1.
Examples
The input and output for Example 1 are as follows.
Input Example 1
4
5
1 2
3 1
3 2
3 4
4 1
Output Example 1
3
4
1
2
0
The input and output for Example 2 are as follows.
Input Example 2
3
2
2 1
2 3
There are two output data for this input data. Either is acceptable.
Output Example 2
2
1
3
1
2
3
1
1
The above problem statement and test data are from
the Information Olympiad Japan Committee
.