잭 에드먼즈

잭 에드먼즈는 미국의 컴퓨터 과학자다. 알고리즘 대회를 준비하는 사람에게는 최대 유량 문제를 $O(|V||E|^2)$에 푸는 에드먼즈-카프 알고리즘의 공동 고안자로 익숙하다. 그가 남긴 더 큰 기여는 코브햄-에드먼즈 논제일지도 모른다. 이 논제는 알고리즘이 실용적인지 판단하는 기준으로 다항 시간을 정의했다. 오늘날 우리는 P(결정론적 다항 시간)에 속한 문제를 효율적으로 풀 수 있는 문제로, NP(비결정론적 다항 시간)에 속한 문제를 효율적으로 검증할 수 있는 문제로 본다. P 대 NP 문제는 P와 NP가 같은지 묻는다. 컴퓨터 과학의 가장 큰 미해결 문제이고, 밀레니엄 문제 일곱 개 중 하나다. 대부분의 컴퓨터 과학자는 P $\ne$ NP라고 믿지만 아직 아무도 증명하지 못했다. 반대로 여러 사람이 어떤 NP-난해 문제가 P에 속함을 보여 P = NP를 증명하려 했고, 모두 실패했다.

외판원 문제는 NP-난해 문제의 한 예다. 목적지 목록과 모든 목적지 쌍 사이의 거리가 주어졌을 때, 출발지에서 시작해 모든 목적지를 방문하고 출발지로 돌아오는 가장 짧은 경로를 찾는 문제다. 그런데 이 문제에는 지도가 없다. 목적지의 좌표만 주어지고 도로는 아직 하나도 놓이지 않았다.

도로는 시장이 놓아 준다. 시장은 단순하고 게으르다. 도로 하나는 두 목적지 $(x_i, y_i)$와 $(x_j, y_j)$를 가로와 세로 선분만으로 직접 잇고, 그래서 길이가 $|x_i - x_j| + |y_i - y_j|$다. 또 도로를 $n - 1$개보다 많이 놓지는 않는다. 어떤 도로를 놓을지는 당신이 정한다.

이동은 놓인 도로만 이용한다. 같은 도로를 여러 번 지나도 되고, 같은 목적지를 여러 번 거쳐도 된다. 첫 번째 목적지에서 출발해 모든 목적지를 방문하고 첫 번째 목적지로 돌아오는 가장 짧은 경로의 길이를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 20$)

각 테스트 케이스의 첫째 줄에 목적지의 개수 $n$이 주어진다. ($1 \le n \le 10\,000$) 다음 $n$개 줄에 목적지 하나의 좌표 $x$와 $y$가 공백으로 구분되어 주어진다. ($-1\,000 \le x, y \le 1\,000$) 가장 먼저 주어지는 목적지가 출발지다. 두 목적지의 좌표가 같을 수도 있다.

각 테스트 케이스마다 모든 목적지를 방문하고 출발지로 돌아오는 가장 짧은 경로의 길이를 한 줄에 출력한다.