출근하기 (Large)

$T$ 번 도시에 있는 회사에 직원 $E$ 명이 다닌다. 직원들이 사는 도시는 이 지역에 모두 $N$ 개 있다. 모든 직원이 회사가 있는 $T$ 번 도시까지 갈 수 있게 하되, 도로를 달리는 자동차 수는 최소로 하려고 한다.

이동 규칙은 다음과 같다.

직원이 도시 사이를 이동하는 방법은 직원 소유의 자동차를 타는 것뿐이다.
직원은 자기와 같은 도시에 사는 직원의 차만 얻어 탈 수 있다.
운전하는 직원은 정원이 $P$ 명인 자동차를 몬다. 정원에는 운전자 본인이 포함되므로 $P = 1$ 이면 운전자 혼자만 탈 수 있다. $P = 0$ 이면 운전면허가 없어서 운전하지 못한다.
사용하는 자동차 수는 최소여야 한다.

회사가 있는 $T$ 번 도시에 사는 직원은 이미 회사에 있으므로 자동차가 필요 없다.

모든 직원이 출근할 수 있는지 판별하고, 가능하면 각 도시에서 회사로 출발하는 자동차가 몇 대인지 구하라.

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

각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 지역의 도시 수 $N$ 과 회사가 있는 도시 번호 $T$ 가 공백을 사이에 두고 주어진다.
다음 줄에 직원 수 $E$ 가 주어진다.
이어지는 $E$ 개의 줄에 직원 한 명의 정보가 한 줄씩 주어진다. 각 줄에는 그 직원이 사는 도시 번호 $H$ 와 그 직원이 모는 자동차의 정원 $P$ 가 공백을 사이에 두고 주어진다. 운전면허가 없으면 $P$ 는 $0$ 이다.

제한

입력에 주어진 순서대로 테스트 케이스마다 한 줄씩 출력한다. 각 줄은 문자열 Case #X: 로 시작하고, $X$ 는 $1$ 부터 시작하는 테스트 케이스 번호다. 그 뒤에 다음 둘 중 하나를 이어서 출력한다.