Ganggangsullae Circle

N students stand in a circle while holding hands. Each student has exactly one student on the left. If that left neighbor is not a friend, the student feels embarrassed.

The total embarrassment of an arrangement is the number of students whose left neighbor is not their friend. Given the friendship relations, write a program that places the students in a circle so that the total embarrassment is minimized.

The first line contains the number of students n and the number of friendship relations m.

Each of the next m lines contains the numbers of two students who are friends. No friendship relation is repeated, and no relation from a student to themself is given. Student numbers are from 1 to n.

Print the minimum possible embarrassment on the first line.

On the second line, print n student numbers in the order they stand around the circle. The first and last printed students are also holding hands.

• 3 ≤ n ≤ 1,000
• (n-1)×(n-2)/2 + 2 ≤ m ≤ n×(n-1)/2