롤러코스터 운행 계획 (Large)

문제

새로 만든 롤러코스터가 곧 개장한다. 열차는 한 줄로 놓인 좌석 $N$ 개로 이루어져 있고, 좌석에는 앞에서 뒤로 1번부터 $N$ 번까지 번호가 붙어 있다. 앞쪽 좌석일수록 값이 비싸다. 개장일 표는 이미 다 팔렸다. 표 한 장은 특정 손님이 지정된 좌석에 앉아 한 번 타는 권리를 뜻한다. 표를 여러 장 산 손님도 있고, 그런 손님은 표 한 장마다 한 번씩 타기를 기대한다.

개장일에 열차를 몇 번 운행할지 정해야 한다. 한 번 운행할 때 좌석마다 손님이 최대 한 명 앉고, 빈 좌석이 있어도 된다. 같은 운행에서 한 손님을 두 좌석에 앉힐 수 없고, 한 좌석에 두 손님을 앉힐 수도 없다.

운영비를 아끼려면 모든 표를 소화하는 데 필요한 운행 횟수를 최소로 만들어야 한다. 운행 횟수를 줄이려고 표를 원하는 만큼 승급시킬 수 있다. 표를 승급시킨다는 것은 손님의 표를 회수하고 더 앞쪽 좌석, 즉 번호가 더 작은 좌석의 표를 새로 주는 것이다. 승급이 잦으면 손님이 다음에도 승급을 요구하므로 승급 횟수도 되도록 적어야 한다.

팔린 표의 좌석과 구매자가 주어진다. 승급을 마음껏 쓰고 운행을 최적으로 짰을 때 모든 표를 소화하는 데 필요한 최소 운행 횟수와, 그 운행 횟수를 지키면서 필요한 최소 승급 횟수를 구하라. 어떤 손님의 표를 4번 좌석에서 2번 좌석으로 옮기는 것은 승급 두 번이 아니라 한 번으로 센다.

입력

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

각 테스트 케이스의 첫 줄에는 정수 $N$ , $C$ , $M$ 이 주어진다. $N$ 은 롤러코스터의 좌석 수, $C$ 는 손님 수, $M$ 은 팔린 표의 수다. 손님은 1번부터 $C$ 번까지 번호로 구분한다. 다음 $M$ 개 줄에는 각각 정수 $P_i$ 와 $B_i$ 가 주어진다. $P_i$ 는 $i$ 번째 표에 배정된 좌석 번호이고, $B_i$ 는 그 표를 산 손님의 번호다.

제한

$1 \le T \le 100$
$2 \le N \le 1000$
$1 \le M \le 1000$
$1 \le P_i \le N$
$2 \le C \le 1000$
$1 \le B_i \le C$

출력

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄씩 출력한다. $x$ 는 테스트 케이스 번호이고 1부터 시작한다. $y$ 는 승급과 운행 일정을 최적으로 정했을 때 모든 표를 소화하는 데 필요한 최소 운행 횟수이고, $z$ 는 운행을 $y$ 번만 해서 모든 표를 소화하는 데 필요한 최소 승급 횟수다.

힌트

예제의 1번 테스트 케이스에서는 두 손님이 모두 2번 좌석 표를 샀다. 한 번만 운행해서 두 표를 다 소화할 수는 없지만, 둘 중 한 표를 1번 좌석으로 승급시키면 한 번 운행에 두 손님이 모두 탄다.

2번 테스트 케이스도 사정이 비슷하지만 두 표가 모두 1번 좌석이다. 1번 좌석보다 앞쪽은 없고 더 못한 좌석으로 바꿔 줄 수도 없으므로, 손님마다 한 번씩 모두 두 번 운행해야 한다.

3번 테스트 케이스는 한 손님이 좌석 두 개를 모두 샀다. 그 손님 때문에 운행이 두 번 필요하므로 승급을 해 줄 이유가 없다.

4번 테스트 케이스처럼 표가 한 장도 없는 손님이나 좌석이 있을 수 있다. 여기서는 3번 좌석 표가 세 장 팔렸다. 예를 들어 2번 손님을 2번 좌석으로 승급시키면, 첫 운행에는 1번 손님이 2번 좌석에 3번 손님이 3번 좌석에 앉고, 둘째 운행에는 2번 손님이 2번 좌석에 1번 손님이 3번 좌석에 앉는다. 승급을 더 해도 운행 횟수는 줄지 않는다. 1번 손님의 표가 두 장이라 좌석과 무관하게 서로 다른 운행에서 소화해야 하기 때문이다.

5번 테스트 케이스에서는 3 1 표 중 하나를 1 1로 승급시키는 것이 최적해 중 하나다.