Das perfekte Array erstellen
Sie unterstützen eine befreundete Informatikerin bei einem Forschungsprojekt. Das Projekt erfordert ein Array, das eine bestimmte Menge von Bedingungen erfüllt. Konkret erhalten Sie
p Paare von Indizes i und j, wobei i und j Positionen in einem Array a der Länge n sind. Jedes Paar (i, j) legt die Bedingung fest, dass kleiner sein muss als . Ihre Aufgabe ist es, ein Array a zu finden, das alle diese Vorgaben erfüllt.Die Ganzzahlen im Array
a müssen zwischen 1 und (einschließlich) liegen.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (2 ≤ n ≤ ) und p (1 ≤ p ≤ ), wobei n die Länge des Arrays a und p die Anzahl der Paare ist.
Auf jede dieser Zeilen folgen p weitere Zeilen, die jeweils zwei durch ein Leerzeichen getrennte ganze Zahlen i und j (1 ≤ i < j ≤ n) enthalten. Diese Paare geben die Indizes an, für die die Bedingung gilt.Ausgabe
Falls es möglich ist, ein Array
a zu finden, das alle vorgegebenen Bedingungen erfüllt, geben Sie in einer Zeile n durch Leerzeichen getrennte ganze Zahlen aus, die dieses Array a repräsentieren. Die Zahlen im Array a müssen zwischen 1 und (einschließlich) liegen.
Wenn es mehrere gültige Lösungen gibt, darf jede beliebige davon ausgegeben werden.Ist es nicht möglich, ein solches Array zu konstruieren, soll das Programm
Impossible ausgeben.Beispiele
Eingabe | Ausgabe |
4 2
1 2
4 1 | 2 3 4 1 |
5 5
1 2
2 3
3 4
5 4
2 5 | 2 4 6 8 5 |
3 3
1 2
2 3
3 1 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB