Construindo o Array Perfeito
Estás a ajudar um amigo, que é cientista informático, num projeto de investigação. O projeto requer encontrar um array que cumpra um conjunto específico de restrições. Concretamente, são-te fornecidos
p pares de índices i e j, em que i e j são índices de um array a de comprimento n. Cada par (i, j) indica a restrição de que deve ser menor do que . A tua tarefa é descobrir um array a que satisfaça todas estas restrições.Os inteiros pertencentes ao array
a devem variar de 1 a (inclusive).Entrada
A primeira linha da entrada contém dois inteiros
n (2 ≤ n ≤ ) e p (1 ≤ p ≤ ), onde n é o tamanho do array a e p é o número de pares.
Cada uma das p linhas seguintes contém dois inteiros i e j separados por espaço (1 ≤ i < j ≤ n), representando os pares de índices que devem satisfazer a restrição .Saída
Se for possível encontrar um array
a que satisfaça todas as restrições dadas, imprime numa única linha n inteiros separados por espaço, representando o array a. Os inteiros em a devem estar entre 1 e (inclusive).
Se existir mais de uma solução possível, podes apresentar qualquer uma delas.Se não for possível encontrar tal array, o programa deve imprimir
Impossible.Exemplos
Entrada | Saída |
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