롤러코스터 운행 일정

당신은 곧 개장할 새로운 롤러코스터를 만들었다. 열차에는 앞에서 뒤로 1부터 N까지 번호가 매겨진 N개의 좌석이 한 줄로 배치되어 있다. 물론 앞쪽에 가까운 좌석일수록 더 가치가 높다. 고객들은 이미 개장일 표를 구매했다. 각 표는 특정 고객이 롤러코스터의 특정 좌석에서 한 번 탑승할 수 있게 한다. 일부 고객은 표를 하나보다 많이 샀을 수 있으며, 표마다 한 번씩 탑승하기를 기대한다.

개장일에 롤러코스터를 몇 번 운행할지 결정해야 한다. 각 운행에서는 각 좌석에 고객 한 명이 앉을 수 있으며, 일부 좌석은 비어 있을 수도 있다. 같은 운행에서 한 고객에게 하나보다 많은 좌석을 배정할 수 없으며, 특정 운행의 같은 좌석에 고객 두 명을 앉힐 수도 없다.

운영 비용을 줄이기 위해 모든 표를 이행하는 데 필요한 운행 횟수를 최소화하고자 한다. 필요한 운행 횟수를 줄이기 위해 임의의 개수의 표를 승급할 수 있다. 표를 승급한다는 것은 고객의 표를 회수하고 그 고객에게 열차의 더 앞쪽 좌석, 즉 번호가 더 작은 좌석의 새 표를 주는 것을 의미한다. 승급이 너무 많으면 고객들이 욕심을 내어 앞으로 더 많은 승급을 요구할 수도 있으므로, 승급하는 표의 수는 가능한 한 적게 하고자 한다.

판매된 모든 표의 좌석 위치와 구매자가 주어질 때, 필요한 만큼 승급하고 운행 일정을 최적으로 정하여 모든 표를 이행하는 데 필요한 최소 운행 횟수는 얼마인가? 또한 그 운행 횟수를 달성하는 데 필요한 최소 표 승급 횟수는 얼마인가? 예를 들어, 특정 운행에서 특정 고객을 좌석 4에서 좌석 2로 승급하는 것은 서로 별개의 두 번이 아니라 단 한 번의 승급으로 센다는 점에 유의하라.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 2 ≤ N ≤ 1000. 1 ≤ M ≤ 1000. 1 ≤ $P_{i}$ ≤ N. 1 ≤ $B_{i}$ ≤ C.

작은 데이터 세트 (테스트 세트 1 - 공개)

C = 2.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ C ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 N, C, M이 있는 한 줄로 시작한다. N은 롤러코스터의 좌석 수, C는 잠재 고객 수, M은 판매된 표의 수이다. 고객은 1부터 C까지의 번호로 식별된다. 이어서 M개의 줄이 주어지며, 각 줄에는 두 정수 $P_{i}$와 $B_{i}$가 주어진다. 전자는 i번째 표에 배정된 롤러코스터의 좌석 위치이고, 후자는 그 표를 구매한 고객의 식별자이다.

각 테스트 케이스마다 Case #x: y z을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y는 승급을 사용하고 운행 일정을 최적으로 정할 때 모든 표를 이행하는 데 필요한 최소 운행 횟수이며, z는 y번의 운행으로 모든 표를 이행할 수 있도록 하는 데 필요한 최소 승급 횟수이다.

마지막 두 예제 케이스는 작은 데이터 세트에 나타나지 않는다는 점에 유의하라.

케이스 #1에서는 두 고객 모두 위치 2의 표를 구매했다. 한 번의 운행으로 두 표를 모두 이행하는 것은 불가능하지만, 어느 한 표를 위치 1로 승급하면 같은 운행에 두 고객을 모두 태울 수 있다.

케이스 #2도 비슷하지만, 두 표 모두 위치 1의 표이다. 이 표들을 승급하거나 더 나쁜 좌석의 표로 교환할 수 없으므로, 고객마다 한 번씩 총 2번을 별도로 운행해야 한다.

케이스 #3에서는 같은 고객이 두 위치의 표를 모두 구매했다. 그 고객 때문에 2번 운행해야 하므로, 승급을 제공할 이유가 없다.

케이스 #4에서는 표가 하나도 배정되지 않은 고객과 위치가 모두 있을 수 있다는 점에 유의하라. 이 케이스에서는 위치 셋의 표가 세 장 판매되었다. 예를 들어 고객 2을 위치 2로 승급하면, 첫 번째 운행에서는 고객 1이 위치 2에 앉고 고객 3이 위치 3에 앉게 할 수 있으며, 두 번째 운행에서는 고객 2이 위치 2에 앉고 고객 1이 위치 3에 앉게 할 수 있다. 추가로 승급하더라도 운행 횟수를 줄일 수는 없다. 고객 1이 표를 두 장 가지고 있어 좌석 위치와 관계없이 서로 다른 운행에서 그 표들을 이행해야 하기 때문이다.

케이스 #5에서 한 가지 최적해는 3 1개의 표 중 하나를 1 1로 승급하는 것이다.