ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2011, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Стаж пилотов

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
За время командировки Леониду пришлось целых 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, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1888. Стаж пилотов