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.

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.

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”.