Giải bài trực tuyến

Japan chuẩn bị chào đón ACM ICPC World Finals và muốn xây 1 số đường. Japan là 1 hòn đảo với N thành phố ở bờ phía Đông và M thành phần ở bờ phía Tây, (M ≤ 1000, N ≤ 1000). Các thành phố ở mỗi bờ được đánh số từ 1 trở đi theo chiều từ Bắc tới Nam. K superhighways sẽ được xây để nối bờ phía Đông và bờ phía Tây của Japan. Mỗi superhighway là 1 đường thẳng nối 1 thành phố ở bờ Đông và 1 thành phố ở bờ Tây.

Xác định số giao điểm của các đường cao tốc này. Không có 3 đường cao tốc cắt nhau tại 1 điểm.

Dòng đầu của file Input là T - số test. Mỗi test bắt đầu bởi 3 số – N, M, K. Tiếp theo là K dòng, mỗi dòng 2 số mô tả cặp thành phố được nối bởi đường cao tốc (số thứ nhất ở bờ Đông, số thứ hai ở bờ Tây)

Với mỗi test case, in ra 1 dòng có dạng :

Test case "case number": "số giao điểm"

Sample

Input :
1 
3 4 4 
1 4 
2 3 
3 2 
3 1 
Ouput: 
Test case 1: 5