도시 관광 | cho.sh

문제

Albert는 방학 동안 $N$ 개의 도시를 방문할 계획이다 (편의상 도시는 1번부터 $N$번까지 번호가 붙어있다). $N$ 개의 도시들은 기차, 비행기, 유람선, 버스 등 다양한 교통 수단으로 서로 연결되어 있는데, 마침 공교롭게도 $N$ 개의 다른 교통수단이 존재한다 (교통 수단도 편의상 1번부터 $N$번까지 번호가 붙어있다). 구체적으로, $D_{k, i, j}$ 는 도시 $i$ 에서 도시 $j$로 이동할 때 $k$ 번째 교통수단을 사용할 때 걸리는 시간을 나타낸다 - 단, 이 값이 0인 경우 해당 교통수단을 이용해서 $i$ 에서 $j$ 로 이동할 수 없음을 나타낸다. 또한, 이 문제에서는 항상 $D_{k, i, j} = D_{k, j, i}$ 이라 가정한다.

예를 들어, $N = 3$ 이고 $D_{1, \cdot, \cdot} = [[0, 1, 3], [1, 0, 4], [3, 4, 0]]$, $D_{2, \cdot, \cdot} = [[0, 2, 2], [2, 0, 4], [2, 4, 0]]$, $D_{3, \cdot, \cdot} = [[0, 3, 8], [3, 0, 4], [8, 4, 0]]$ 이라 하자.

$D_{1, 1, 2} = 1$ 이므로 1번째 교통수단을 이용하여 도시 1에서 도시 2로 이동하면 1 단위 시간이 걸린다.
$D_{2, 3, 1} = 2$ 이므로 2번째 교통수단을 이용하여 도시 3에서 도시 1로 이동하면 2 단위 시간이 걸린다.
$D_{3, 2, 3} = 4$ 이므로 3번째 교통수단을 이용하여 도시 2에서 도시 3으로 이동하면 4 단위 시간이 걸린다.

다양한 교통수단과 일정을 알아보던 중, Albert는 1번 도시에서 출발하여 각 교통수단을 정확히 한 번씩 이용하고 각 도시를 정확히 한 번씩 방문한 후 다시 1번 도시로 돌아오는 방법 중 가장 시간이 적게 걸리는 경우와 가장 오래 걸리는 경우를 알고 싶어졌다.

위 예제에서 도시 1 -> 도시 2 -> 도시 3 -> 도시 1로 이동하는 방법을 생각해보자.

교통수단을 1, 2, 3 순서로 사용한 경우: $D_{1, 1, 2} + D_{2, 2, 3} + D_{3, 3, 1} = 1 + 4 + 8 = 13$ 단위 시간이 걸린다.
교통수단을 1, 3, 2 순서로 사용한 경우: $D_{1, 1, 2} + D_{3, 2, 3} + D_{2, 3, 1} = 1 + 4 + 2 = 7$ 단위 시간이 걸린다. (이 예제에서 시간이 가장 적게 걸리는 방법이다)
교통수단을 2, 1, 3 순서로 사용한 경우: $D_{2, 1, 2} + D_{1, 2, 3} + D_{3, 3, 1} = 2 + 4 + 8 = 14$ 단위 시간이 걸린다. (이 예제에서 시간이 가장 오래 걸리는 방법이다)
그 외 다양한 방법으로 각 교통수단을 한 번씩 이용하여 각 도시를 한 번씩 방문하고 돌아올 수 있다.

위 예제의 경우 Albert가 원하는 답은 7과 14가 된다. 입력으로 정수 $N$ 과 3차원 배열 $D$가 주어졌을 때, 위 조건을 만족하면서 관광할 때 걸리는 최소/최대 시간을 구해보자.

입력

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$ 이 주어진다. 다음 $N^2$ 줄에 걸쳐 각 줄에 $N$ 개의 정수가 공백으로 구분되어 주어지는데, 처음 $N$ 개의 줄은 1번째 교통 수단을 이용했을 때 도시 $i$ 에서 도시 $j$ 로 이동하는데 걸리는 시간인 $D_{1, \cdot, \cdot}$ 을 나타내고 (해당 $N$ 개의 줄 중 첫 번째 줄은 $i = 1$ 인 경우, 다음 줄은 $i = 2$ 인 경우 등을 나타낸다), 다음 $N$ 개의 줄은 2번째 교통 수단을 이용한 경우를 나타내고, 마찬가지로 $N$ 번째 교통 수단을 이용했을 때 걸리는 시간까지 순서대로 주어진다.

출력

각 테스트 케이스의 정답인 최소 시간과 최대 시간을 공백으로 구분하여 각 줄에 출력한다. 단, 조건을 만족하면서 관광할 방법이 없는 경우 "0 0"을 출력한다 (따옴표 제외).

제한

$1 \le T \le 10$
$2 \le N \le 8$
$1 \le i, j, k \le N$ 인 $i,j,k$ 에 대하여: $0 \le D_{k, i, j} \le 10^6$
$1 \le i, j, k \le N$ 인 $i,j,k$ 에 대하여: $D_{k, i, j} = D_{k, j, i}$ 임이 보장된다.
$1 \le i, k \le N$ 인 $i,k$ 에 대하여: $D_{k, i, i} = 0$ 임이 보장된다.