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
input | output |
---|
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