ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

NEERC 2011, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Pilot Work Experience

Time limit: 1.0 second
Memory limit: 64 MB
Leonid had n Oceanic Airlines flights during his business trip. He studied the latest issue of the monthly on-board magazine of this company from cover to cover. In particular, he learned about the rules of forming an airplane crew. It turned out that the work experience of the captain (i.e., the number of complete years of work in civil aviation) was always greater by exactly one than the work experience of the second pilot.
The Oceanic Airlines company does not disclose information on the work experience of their pilots. Leonid is interested in the largest possible difference between the work experiences of pilots on the flights he had. He has written the names of the two pilots on each flight but couldn't remember who was the captain and who was the second pilot. Leonid assumes that the work experience of each pilot is in the range from 1 to 50 years and that the work experiences didn't change in the period between his first and last flights with Oceanic Airlines.
Help Leonid use the available information to find out the maximum possible difference in the work experiences of pilots on the flights he had.

Input

The first line contains integers n and p, which are the number of flights Leonid had and the number of pilots flying the planes on these flights (2 ≤ n ≤ 1 000; 2 ≤ p ≤ 50). The pilots are numbered from 1 to p. In the ith of the following n lines you are given two different integers denoting the pilots of the ith flight.

Output

In the first line output the maximum possible difference in the work experiences of the pilots. In the second line output p integers. The ith integer must be the work experience of the ith pilot. If there are several possible answers, output any of them. If Leonid is wrong in his assumptions or his data are incorrect, output “-1”.

Samples

inputoutput
4 4
1 2
3 1
2 4
3 4
2
1 2 2 3
3 3
1 2
2 3
1 3
-1
Problem Author: Magaz Asanov
Problem Source: NEERC 2011, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1888. Pilot Work Experience