За время командировки Леониду пришлось целых n раз летать самолётами Oceanic Airlines. Он изучил последний выпуск ежемесячного журнала этой авиакомпании от корки до корки и благодаря этому ознакомился с правилами, по которым формируется экипаж самолёта. Оказалось, что стаж первого пилота (количество полных лет, которые он проработал в гражданской авиации) всегда ровно на год больше стажа второго пилота.

Авиакомпания Oceanic Airlines не разглашает информацию о стаже пилотов воздушного судна. Леониду стало интересно, насколько велика может быть разница в стаже пилотов всех рейсов, которыми он летал. Чтобы определить это, он выписал фамилии двух пилотов каждого рейса, но не смог вспомнить, кто из пилотов являлся первым, а кто — вторым. Леонид считает, что стаж каждого пилота не может быть меньше одного года или больше пятидесяти лет и что в промежутке между его первым и последним полётом ни у одного пилота не изменился стаж.

Помогите Леониду по этой информации найти максимальную возможную разницу в стаже пилотов самолётов, на которых он летал.

В первой строке записаны целые числа n и p — количество полётов, совершённых Леонидом, и количество пилотов, которые управляли самолётами в этих полётах (2 ≤ n ≤ 1 000; 2 ≤ p ≤ 50). Пилоты занумерованы целыми числами от 1 до p. В i-й из следующих n строк записаны два различных целых числа — номера пилотов, выполнявших i-й рейс.

В первой строке выведите максимальную возможную разницу в стаже пилотов. Во второй строке выведите p чисел, i-е число должно быть равно стажу i-го пилота. Если есть несколько вариантов ответа, выведите любой из них. Если Леонид заведомо ошибся в своих предположениях или его данные неверны, выведите «-1».