문제
이 세상에는 수많은 컴퓨터들이 통신망을 통해 서로 연결되어 정보를 교류하고 있다. 오늘 플레이어는 이 거대한 통신망 중 한 구역을 조사하고자 한다.
플레이어가 조사할 구역에는 개의 컴퓨터가 있고,
개의 통신 회선이 있다. 각 컴퓨터는
번부터
번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다.
컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다.
플레이어는 여러 개의 컴포넌트 중, 가장 밀도가 높은 컴포넌트를 조사하려고 한다. 컴포넌트의 밀도는 그 컴포넌트에 포함된 통신 회선의 개수를 컴퓨터의 수로 나눈 값이다. 주어진 통신 구역을 분석해서, 가장 밀도가 높은 컴포넌트의 정보를 출력해보자.
예제 설명
첫 번째 예제에서 주어진 통신 구역에는 두 개의 컴포넌트가 있다. 한 컴포넌트는 (1, 3, 5, 7)번 컴퓨터로 이루어져 있고, 다른 컴포넌트는 (2, 4, 6)번 컴포넌트로 이루어져 있다.
(1, 3, 5, 7)번 정점으로 구성된 컴포넌트에는 네 개의 통신 회선이 존재하므로, 이 컴포넌트의 밀도는 이다. (2, 4, 6)번 컴퓨터로 구성된 컴포넌트에는 두 개의 통신 회선이 존재하므로, 이 컴포넌트의 밀도는
이다. 먼저 주어진 컴포넌트의 밀도가 더 크므로, 1 3 5 7을 답으로 출력해야 한다.
입력
첫째 줄에 컴퓨터의 개수 과 통신 회선의 개수
이 공백을 두고 주어진다.
다음 개의 줄에는 통신 회선이 잇는 두 정점
가 공백을 두고 주어진다.
- 같은 두 컴퓨터 쌍을 연결하는 통신 회선은 최대 하나이다.
- 입력에서 주어지는 모든 수는 정수이다.
출력
아래 조건을 만족하는 컴포넌트에 포함된 컴퓨터의 번호를 오름차순으로 공백을 두고 출력한다.
- 가장 밀도가 높은 컴포넌트를 출력한다.
- 1을 만족하는 컴포넌트가 여러 개라면, 컴포넌트를 구성하는 컴퓨터의 수가 가장 작은 컴포넌트를 출력한다.
- 2를 만족하는 컴포넌트가 여러 개라면, 더 작은 번호를 가진 컴퓨터가 있는 컴포넌트를 출력한다.