Creare l’Array Perfetto
Stai aiutando un amico, che è un informatico, in un progetto di ricerca. L’obiettivo è trovare un array che soddisfi una serie di vincoli specifici. In particolare, ti vengono date
p coppie di indici i e j, dove i e j sono indici di un array a di lunghezza n. Ogni coppia (i, j) indica il vincolo per cui deve essere minore di . Il tuo compito è trovare un array a che rispetti tutte queste condizioni.Gli interi nell’array
a devono essere compresi tra 1 e (inclusi).Input (Ingresso)
La prima riga dell’input contiene due interi
n (2 ≤ n ≤ ) e p (1 ≤ p ≤ ), dove n è la lunghezza dell’array a e p è il numero di coppie.Output (Uscita)
Se esiste almeno un array
a che soddisfa tutti i vincoli, stampa una singola riga contente n interi separati da uno spazio, corrispondenti all’array a. Gli elementi di a devono essere compresi tra 1 e (inclusi).Se esistono più soluzioni possibili, va bene stamparne una qualunque.
Esempi
Input | Uscita |
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