Построение идеального массива
Вы помогаете вашему другу, который занимается компьютерными науками, в исследовательском проекте. Этот проект требует найти массив, удовлетворя определённому набору ограничений. В частности, вам даны
p пар индексов i и j, где i и j — это индексы массива a длины n. Каждая пара (i, j) указывает, что должен быть меньше . Ваша задача — найти такой массив a, который соответствует всем заданным условиям.Числа в массиве
a должны находиться в диапазоне от 1 до включительно.Входные данные
Первая строка входных данных содержит два целых числа
n (2 ≤ n ≤ ) и p (1 ≤ p ≤ ), где n — это длина массива a, а p — это количество пар.
Каждая из следующих p строк содержит по два целых числа i и j, разделённых пробелом (1 ≤ i < j ≤ n), которые обозначают, что должно выполняться условие .Выходные данные
Если можно построить массив
a, удовлетворя всем ограничениям, выведите в одной строке n целых чисел, разделённых пробелом, представляющих массив a. Значения в массиве a должны находиться в диапазоне от 1 до включительно.
Если существует несколько подходящих решений, можно вывести любое из них.Если найти подходящий массив невозможно, необходимо вывести
Impossible.Примеры
Ввод | Вывод |
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