강강술래

시간 제한1초메모리 제한512 MB

요약

매우 촘촘한 친구 관계 그래프에서 원형으로 배치했을 때 왼쪽 이웃이 친구가 아닌 학생 수를 최소화하는 배치를 찾는 문제입니다.

문제

N명의 학생이 서로 손을 잡고 원형으로 선다. 각 학생에게는 왼쪽에 선 학생이 한 명씩 있으며, 그 왼쪽 학생과 친분이 없으면 그 학생은 부끄러움을 느낀다.

전체 부끄러움도는 왼쪽 학생과 친분이 없는 학생의 수이다. 학생들의 친분 관계가 주어질 때, 전체 부끄러움도가 최소가 되도록 학생들을 원형으로 세우는 프로그램을 작성하라.

첫째 줄에 학생 수 n과 친분 관계의 수 m이 주어진다.

다음 m개의 줄에는 서로 친분 관계가 있는 두 학생의 번호가 주어진다. 같은 친분 관계가 두 번 주어지지 않으며, 자기 자신과의 친분 관계도 주어지지 않는다. 학생 번호는 1부터 n까지이다.

첫째 줄에 가능한 최소 부끄러움도를 출력한다.

둘째 줄에는 원형으로 선 순서대로 학생 번호 n개를 출력한다. 둘째 줄의 첫 번째 학생과 마지막 학생도 서로 손을 잡고 있다.