За время командировки Леониду пришлось целых n раз летать
самолётами Oceanic Airlines. Он изучил последний выпуск ежемесячного
журнала этой авиакомпании от корки до корки и благодаря этому ознакомился с правилами, по которым
формируется экипаж самолёта. Оказалось, что стаж первого пилота (количество полных лет, которые
он проработал в гражданской авиации) всегда ровно на год больше стажа второго пилота.
Авиакомпания Oceanic Airlines не разглашает информацию о стаже пилотов
воздушного судна. Леониду стало интересно, насколько велика может быть
разница в стаже пилотов всех рейсов, которыми он летал.
Чтобы определить это, он выписал фамилии двух пилотов каждого рейса, но
не смог вспомнить, кто из пилотов являлся первым, а кто — вторым.
Леонид считает, что стаж каждого
пилота не может быть меньше одного года или больше пятидесяти лет и что в
промежутке между его первым и последним полётом ни у одного пилота не изменился стаж.
Помогите Леониду по этой информации найти максимальную возможную
разницу в стаже пилотов самолётов, на которых он летал.
Исходные данные
В первой строке записаны целые числа n и p — количество полётов, совершённых
Леонидом, и количество пилотов, которые управляли самолётами в этих полётах
(2 ≤ n ≤ 1 000; 2 ≤ p ≤ 50). Пилоты занумерованы целыми числами от 1 до p. В i-й из
следующих n строк записаны два различных целых числа — номера пилотов, выполнявших i-й рейс.
Результат
В первой строке выведите максимальную возможную разницу в стаже пилотов. Во второй
строке выведите p чисел, i-е число должно быть равно стажу
i-го пилота. Если есть несколько вариантов ответа, выведите любой из них. Если
Леонид заведомо ошибся в своих предположениях или его данные неверны, выведите «-1».
Примеры
исходные данные | результат |
---|
4 4
1 2
3 1
2 4
3 4
| 2
1 2 2 3
|
3 3
1 2
2 3
1 3
| -1
|
Автор задачи: Магаз Асанов
Источник задачи: NEERC 2011, Четвертьфинал Восточного подрегиона