이분 그래프 놀이

Bob은 이분 그래프 (Bipartite Graph)를 이용한 놀이를 즐겨한다. 이 문제에서는 아래와 같이 임의의 이분 그래프 $H = (X + Y, E)$를 정의한다:

• $n$개의 노드 집합 $X = \\{x\_1, x\_2, \dots, x\_n \\}$ 과 $m$개의 노드 집합 $Y = \\{ y\_1, y\_2, \dots, y\_m\\}$ 은 분리되어 있고, 따라서 $H$의 모든 간선은 $X$의 노드 중 하나와 $Y$의 노드 중 하나를 연결한다.
• 간선 집합은 $E = \\{ e\_1, e\_2, \dots, e\_k \\}$로 나타낸다.

Bob은 아래 규칙에 따라 이분 그래프 놀이를 한다:

• $X$의 각 노드 $x\_i$에 서로 다른 1부터 n 사이의 정수 가중치 $v\_i$를 부여한다. (즉, $1 \leq i \leq n$ 인 $i$에 대하여 $1 \leq v\_i \leq n$, $v\_i \in \mathbb{Z}$ 이고 $i \neq j$ 일 때 $v\_i \neq v\_j$ 이다.)
• $Y$의 각 노드 $y\_j$에 서로 다른 1부터 m 사이의 정수 가중치 $w\_j$를 부여한다 (즉, $1 \leq j \leq m$인 $j$에 대하여 $1 \leq w\_j \leq m$, $w\_j \in \mathbb{Z}$ 이고 $i \neq j$ 일 때 $w\_i \neq w\_j$ 이다.)
• 위 가중치를 토대로 각 간선 $e = (x\_i, y\_j)$ 에 대해 간선의 가중치는 $v\_i + w\_j$ 로 정의한다.
• 이분 그래프 H의 "점수"는 모든 간선의 가중치 합으로 정의한다.

예를 들어 X = {x1, x2}, Y = {y1, y2}, E = {(x1, y1), (x2, y1), (x2, y2)}라 하자 (아래 그림 참고).

이 때 위 규칙에 따라 노드들에 가중치를 부여하는 방법은 총 2! × 2! = 4가지 존재한다.

• 만약 v1 = 1, v2 = 2이고 w1 = 1, w2 = 2라면: e1 = v1 + w1 = 2, e2 = v2 + w1 = 3, e3 = v2 + w2 = 4가 되어 H의 점수는 9가 된다.
• 만약 v1 = 1, v2 = 2이고 w1 = 2, w2 = 1라면: e1 = v1 + w1 = 3, e2 = v2 + w1 = 4, e3 = v2 + w2 = 3가 되어 H의 점수는 10이 된다.
• 만약 v1 = 2, v2 = 1이고 w1 = 1, w2 = 2라면: e1 = v1 + w1 = 3, e2 = v2 + w1 = 2, e3 = v2 + w2 = 3가 되어 H의 점수는 8이 된다.
• 만약 v1 = 2, v2 = 1이고 w1 = 2, w2 = 1라면: e1 = v1 + w1 = 4, e2 = v2 + w1 = 3, e3 = v2 + w2 = 2가 되어 H의 점수는 9가 된다.

H의 "최대 점수"는 위와 같이 가능한 모든 가중치를 부여하는 방법 중 H의 점수를 최대화 했을 때 얻을 수 있는 점수로 정의하자 -- 편의상 이를 S(H)라 하자. Bob은 임의의 이분 그래프 H의 "최대 점수"를 구하는 놀이를 즐겨하지만 이제 너무 잘하게 되어 지루해하던 참이다.

마침 이를 지켜보던 Alice는 새로운 놀이를 제안했다. 그래프 H의 간선 중 임의로 i번째 간선을 지워 새로운 이분 그래프를 얻을 수 있는데, 이를 Hi라 하자 (아래 그림 참고).

S(Hi)는 그래프 Hi의 "최대 점수"이며 상기한 정의에 따라 구할 수 있다. 예를 들어 위의 예제에서 H1은 원래 그래프 H에서 (x1, y1)을 삭제한 그래프이며, 이 때 S(H1)은 7이다 (이를 달성하려면 v1 = 1, v2 = 2 이어야 한다). 같은 예제에서 H2은 (x2, y1)을 삭제한 그래프이며, 이 때 (v1, v2, w1, w2) 값에 관계없이 S(H2)는 6이다. S(H3)은 7이며, 따라서 이 경우 S(H1), S(H2), S(H3) 의 최댓값은 7이다.

Alice의 제안대로 Bob은 S(H)뿐 아니라 S(H1), S(H2), ..., S(Hk)의 최댓값을 구해보려고 한다. Bob을 도와주자.

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

각 테스트 케이스의 첫 줄에는 n, m, k가 공백으로 구분되어 주어진다. 다음 k개의 줄에는 각 줄에 간선을 나타내는 2개의 정수가 공백으로 구분되어 주어지며 X의 노드 인덱스와 Y의 노드 인덱스를 나타낸다 (즉, xi와 yj를 잇는 간선은 "i j"로 주어진다).

각 테스트 케이스의 정답인 두 개의 정수를 각 줄에 출력한다. 첫 번째 정수는 S(H)이며 두 번째 정수는 S(H1), ..., S(Hk)의 최댓값이다.

• 1 ≤ T ≤ 10
• 1 ≤ n, m ≤ 10,000
• 1 ≤ k ≤ 100,000