Swiss Olympiad in Informatics

Stofl befindet sich zur Zeit an der Universität von Waterloo in Kanada für ein Austauschsemester. Da Hockey in Kanada extrem beliebt ist, wurde er auch da hineingezogen. Er wurde sogar ausgewählt, ein Hockeyturnier mit allen regionalen Mannschaften zu organisieren. Stofl hat den Spielplan für die ersten paar Wochen des Turniers bereits vorbereitet (ein Spiel pro Tag), und einige Spiele fanden bereits statt. Er hat geplant, jedes Team gegen jedes andere spielen zu lassen. Dies führt zu total n*(n-1)/2 Spielen, von welchen k bereits stattgefunden haben. Da das Turnier länger dauert als Stofl zuerst erwartet hat, beginnt er sich zu langweilen und möchte das Turnier bereits jetzt abbrechen, aber nur wenn er eine faire Rangliste aller Teams aufstellen kann. Das heisst, er muss alle Teams miteinander vergleichen können, auch wenn nicht jedes Team gegen jedes andere Team gespielt hat. Es gibt keine zwei gleichstarke Teams. Zwei Mannschaften können entweder über die Direktbegegnung (sie spielten gegeneinander) verglichen werden, oder indirekt über einige andere Teams. Wenn zum Beispiel A bereits B geschlagen hat und B gegen C gewonnen hat, wissen wir, dass A auch C schlagen würde.

Gegeben sind die k schon ausgetragenen Spiele in chronologischer Reihenfolge. Berechne ob Stofl das Turnier schon abbrechen kann und wenn ja, bestimme den frühest möglichen Tag, an dem das Turnier hätte gestoppt werden können, und gib die Rangliste aus.

Die erste Zeile enthält zwei ganze Zahlen n, 2≤n≤1000, und k, 1≤k≤20000 (und k≤n*(n-1)/2). Die folgenden k Zeilen enthalten zwei ganze Zahlen x_i und y_i, 1≤x_i,y_i≤n, x_i/=y_i, der Match, der am i-ten Tag des Turniers gespielt gespielt wurde. Das Team, dessen Nummer zuerst genannt ist, hat den Match gewonnen.

Wenn dein Programm für alle Testfälle mit n ≤ 50 korrekt funktioniert (im gegebenen Zeitlimit), erhältst du mindestens die Hälfte der Punkte für diese Aufgabe.

Gib den frühest möglichen Tag aus, an dem Stofl die definitive Rangliste gewusst hätte. Wenn die Rangliste nach den k ausgetragenen Spielen noch nicht bestimmt werden kann, gib -1 aus.

Wenn die Rangliste bestimmt werden kann, gib sie auf den nächsten n Zeilen aus. Die i-te dieser Zeilen sollte eine einzelne ganze Zahl enthalten, nämlich die Nummer des Teams auf dem i-ten Platz.

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

4
1
2
4
3

• Du kannst annehmen, dass es keine zwei gleichstarken Teams gibt, sodass eine exakte Rangliste möglich ist (nachdem genug Spiele gespielt sind). Das stärkere Team gewinnt immer gegen das schwächere Team.
• Der Spielplan ist korrekt, das heisst Team A spielt gegen Team B genau einmal im Turnier. Darum spielt Team A höchstens einmal gegen Team B während den gegebenen ersten k Tagen des Turniers.