회의 준비

회의에 참석하는 사람들의 친분 관계를 바탕으로 하나 이상의 위원회를 구성하려고 한다. 위원회는 다음 조건을 만족해야 한다.

1. 서로 알고 있는 두 사람은 반드시 같은 위원회에 속한다.
2. 가능한 한 많은 위원회를 만든다.

따라서 한 위원회는 친분 관계를 따라 서로 연결된 참석자들의 집합이 된다.

각 위원회에서는 대표를 한 명 뽑는다. 회의 중에는 대표만 발언할 수 있으므로, 참석자는 자신의 의견을 대표에게 전달해야 한다. 참석자는 자신이 직접 알고 있는 사람에게만 의견을 전달할 수 있으며, 필요하면 여러 사람을 거쳐 대표에게 전달한다.

어떤 참석자가 대표에게 의견을 전달할 때 거쳐야 하는 최소 사람 수를 그 참석자의 의사 전달 시간이라고 하자. 한 위원회에서 모든 참석자의 의사 전달 시간 중 최댓값이 최소가 되도록 대표를 정해야 한다.

각 위원회의 대표를 구하는 프로그램을 작성하시오.

예를 들어 1번, 2번, 3번 참석자가 한 위원회에 있고 1번과 2번, 2번과 3번이 서로 알고 있다면, 2번을 대표로 뽑는 것이 가장 좋다. 1번이나 3번을 대표로 뽑으면 반대쪽 끝의 참석자가 한 사람을 거쳐야 하지만, 2번을 대표로 뽑으면 두 참석자 모두 대표에게 직접 전달할 수 있다.

첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자는 1부터 N까지의 자연수로 번호가 붙어 있으며, N은 100 이하이다.

둘째 줄에 서로 알고 있는 관계의 수 M이 주어진다. 이어지는 M개의 줄에는 서로 알고 있는 두 참석자의 번호가 한 줄에 하나씩 주어진다.

첫째 줄에 만들어지는 위원회의 수 K를 출력한다.

다음 K개의 줄에는 각 위원회의 대표 번호를 작은 번호부터 차례로 한 줄에 하나씩 출력한다. 한 위원회에서 대표가 될 수 있는 사람이 둘 이상이면 그중 한 명만 출력하면 된다.