호석이 두 마리 치킨
면접 대비시간 제한1초메모리 제한512 MB
무방향 그래프에서 두 건물에 가게를 세울 때 모든 건물에서 가장 가까운 가게까지의 왕복 시간 합이 최소가 되는 쌍을 찾고, 동점이면 사전순으로 앞선 쌍을 출력한다.
문제
컴공 출신은 치킨집을 하게 되어 있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두 마리 치킨"이다.
이번에 키친 도시에 분점을 내게 된 호석이 두 마리 치킨은 도시 안에 매장 2개를 지으려고 한다. 도시는 N개의 건물과 M개의 도로로 이루어져 있다. 건물에는 1번부터 N번까지 번호가 붙어 있다. i번째 도로는 서로 다른 두 건물 Ai번과 Bi번 사이를 1시간에 양방향으로 이동할 수 있는 도로이다.
키친 도시에서 건물 2개를 골라 치킨집을 열려고 한다. 아무 곳에나 열 수는 없어서 모든 건물에서의 접근성 합을 최소화하려고 한다. 건물 X의 접근성은 X에서 가장 가까운 호석이 두 마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라 치킨집을 열려고 하는 것이다.
컴공을 졸업한 지 30년이 넘는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물이 된 호석이를 위해 최적의 위치가 될 수 있는 건물 2개의 번호와 그때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 번호가 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.
입력
첫 번째 줄에 건물의 개수 N과 도로의 개수 M이 주어진다. 이어서 M개의 줄에 걸쳐 도로의 정보 Ai, Bi가 공백으로 나뉘어 주어진다. 같은 도로가 중복되어 주어지는 경우는 없다. 어떤 두 건물을 잡아도 도로를 따라 오고 가는 방법이 존재함이 보장된다.
출력
한 줄에 치킨집을 지을 건물 2개의 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다.
가능한 건물 조합이 여러 개라면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 것을 출력한다.
제한
- 2 ≤ N ≤ 100
- N-1 ≤ M ≤ N×(N - 1)/2
- 1 ≤ Ai, Bi ≤ N (Ai ≠ Bi)