2323번 - 강강술래 스페셜 저지

강강술래를 하려고 한다. 강강술래는 총 N명이 할 것인데, 이 N명이 서로 손을 잡고 둥굴게 서게 된다. 이때 선 모양에 따라서 부끄러움도가 달라질 수 있다. 부끄러움도는 손을 잡고 있는 왼쪽 사람과 친분관계가 없는 사람의 수이다.

기왕이면 부끄러움도가 작도록 서는 것이 좋을 것이다. 입력으로 학생들의 친분관계가 주어졌을 때, 부끄러움도가 최소가 되도록 학생들을 세우는 프로그램을 작성하시오.

첫째 줄에 n, m이 주어진다. 다음 m개의 줄에는 친분관계가 있는 두 학생의 번호가 주어진다. 친분관계가 중복되어 입력으로 주어지지 않으며, 자기 자신과 친분관계가 있는 경우는 주어지지 않는다. 각 사람의 번호는 1부터 n까지의 자연수이다. 

첫째 줄에 부끄러움도를 출력한다. 다음 줄에는 n개의 수로 서있는 순서대로 학생의 번호를 출력한다. 제일 먼저 출력되는 사람과 제일 마지막에 출력되는 사람이 손을 잡고 있음에 유의한다.

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