Swiss Olympiad in Informatics

Stofl is currently on a student exchange semester at the University of Waterloo (Canada). As hockey is really popular in Canada, he got involved in that as well. In fact he was even chosen to organize a hockey-tourney of all the regional teams. Stofl has prepared the game plan (one match a day) for the first few weeks of the tournament, and some matches already took place. More precisely, he has planned to let each team play against every other team. This leads in total to n*(n-1)/2 matches, k of them already took place.

Since this tournament takes longer than Stofl initially expected, he starts to get bored and wants to stop the tournament early, but only if he can create a ranking of all the teams. That is, he wants to be able to compare all the teams, even if not every team has played against every other team. There are no two teams of equal strength. Two teams can be compared either directly (if they played against each other) or indirectly, over some number of teams.

If, for example, A already defeated B and B defeated C, we know that A would also defeat C.

Given the k matches already played in chronological order, calculate whether Stofl can stop the tournament early and if so, determine the earliest day when the tournament could have been stopped, and output the ranking.

The first line contains two numbers n, 2≤n≤1000, and k, 1≤k≤20000 (and k≤n*(n-1)/2). The following k lines contain two numbers x_i and y_i, 1≤x_i,y_i≤n, x_i/=y_i, namely the match played at the i-th day of the tournament. The team whose number is mentioned first won the match.

Output the earliest day at which Stofl could have known the definitive ranking. If the ranking cannot yet be determined after the k scheduled matches, output -1.

If the ranking can be determined, output the ranking on the next n lines. The i-th of these lines should contain a single integer, the number of the team ranked i-th.

If your program works correctly (in the given time limit) for cases, in which n≤50, you will score at least half the points for this task.

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

4
1
2
4
3

• You can assume that there are no two teams with equal strength, so an exact ranking is possible (after enough matches have been played). Furthermore, the stronger team always wins against a weaker team.
• The tournament-schedule is correct, meaning team A plays against team B exactly once in the tournament. Therefore team A plays against team B at most once during the given first k days of the tournament.

Submission form