롤러코스터 배차 (Small)

새로 만든 롤러코스터가 곧 개장한다. 열차는 앞에서 뒤로 1번부터 $N$번까지 번호가 붙은 좌석 한 줄로 이루어진다. 앞쪽 좌석일수록 값어치가 크다. 개장일 표는 이미 팔렸다. 표 한 장은 지정된 손님 한 명이 지정된 좌석에 앉아 한 번 타는 권리이고, 표를 여러 장 산 손님은 표 수만큼 타기를 기대한다.

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

운행 횟수가 적을수록 비용이 줄어들므로 운행 횟수를 최소로 하려고 한다. 운행 횟수를 줄이려고 표를 원하는 만큼 승급할 수 있다. 표를 승급한다는 것은 그 표를 더 앞쪽 좌석, 즉 번호가 더 작은 좌석의 표로 바꿔 주는 것이다. 승급을 받은 손님은 다음에도 승급을 요구하므로 승급 횟수도 최소로 하려고 한다. 표 한 장을 4번 좌석에서 2번 좌석으로 옮기는 것은 승급 두 번이 아니라 한 번으로 센다.

팔린 표가 모두 주어진다. 승급을 필요한 만큼 하고 운행을 최적으로 배치했을 때 모든 표를 처리하는 데 필요한 최소 운행 횟수와, 그 운행 횟수로 모든 표를 처리하는 데 필요한 최소 승급 횟수를 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 정수 세 개가 주어진다. 열차의 좌석 수 $N$, 손님 후보의 수 $C$, 팔린 표의 수 $M$이다. 손님에게는 1번부터 $C$번까지 번호가 붙어 있다. 이어지는 $M$개의 줄 중 $i$번째 줄에는 정수 두 개 $P_i$와 $B_i$가 주어진다. $P_i$는 $i$번째 표에 지정된 좌석 번호이고, $B_i$는 그 표를 산 손님의 번호이다.

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

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

첫째 예제 케이스에서는 두 손님이 모두 2번 좌석 표를 샀다. 한 번 운행으로는 두 표를 모두 처리할 수 없지만, 둘 중 하나를 1번 좌석으로 승급하면 두 손님이 같은 운행에 탄다.

둘째 예제 케이스도 비슷하지만 두 표가 모두 1번 좌석이다. 1번 좌석 앞에는 좌석이 없고 표를 더 뒤쪽으로 바꿔 줄 수도 없으므로 두 손님은 따로 타야 한다.

셋째 예제 케이스에서는 한 손님이 표 두 장을 모두 샀다. 좌석을 어떻게 바꾸어도 그 손님은 두 번 타야 하므로 승급은 도움이 되지 않는다.

넷째 예제 케이스를 보면 표가 한 장도 없는 좌석과 손님이 있어도 된다. 3번 좌석 표가 세 장 팔렸는데, 2번 손님을 2번 좌석으로 승급하면 한 번은 1번 손님이 2번 좌석, 3번 손님이 3번 좌석에 타고, 다른 한 번은 2번 손님이 2번 좌석, 1번 손님이 3번 좌석에 탄다. 승급을 더 해도 운행 횟수는 줄지 않는다. 1번 손님이 표를 두 장 샀으니 좌석과 무관하게 서로 다른 운행에 타야 하기 때문이다.

다섯째 예제 케이스에서는 3 1 표 두 장 중 하나를 1번 좌석으로 승급하는 것이 최적의 방법 가운데 하나이다.