Construyendo el Arreglo Perfecto
Estás ayudando a un amigo que es científico informático en un proyecto de investigación. El proyecto necesita encontrar un arreglo que cumpla con un conjunto específico de restricciones. En particular, se te dan
p pares de índices i y j, donde i y j son índices de un arreglo a de longitud n. Cada par (i, j) representa una restricción que indica que debe ser menor que . Tu tarea es encontrar un arreglo a que satisfaga todas las restricciones dadas.Los enteros en el arreglo
a deben estar entre 1 y inclusive.Entrada
La primera línea de la entrada contiene dos enteros
n (2 ≤ n ≤ ) y p (1 ≤ p ≤ ), donde n es la longitud del arreglo a y p es el número de pares.
Cada una de las siguientes p líneas contiene dos enteros separados por un espacio, i y j (1 ≤ i < j ≤ n), que representan los pares de índices que deben satisfacer la restricción .Salida
Si existe algún arreglo
a que cumpla todas las restricciones, imprime una sola línea con n enteros separados por espacios, representando el arreglo a. Los enteros en a deben estar entre 1 y inclusive.
Si hay más de una posible solución, puedes imprimir cualquiera de ellas.Si no es posible encontrar un arreglo que satisfaga dichas restricciones, el programa debe imprimir
Impossible.Ejemplos
Entrada | Salida |
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