MSE06H - Japan

## 题目描述 日本计划迎接ACM-ICPC世界总决赛，为此必须修建大量道路。日本是一个高岛，东海岸有N个城市，西海岸有M个城市(M <= 1000, N <= 1000)。将修建K条高速公路。每个海岸的城市编号分别是1、2、……从北到南。每条高速公路都是一条直线，连接着东海岸的城市和西海岸的城市。建设资金由ACM担保。其中很大一部分是由高速公路之间的交叉点数量决定的。两条高速公路最多在一个地点相交。编写一个程序，计算高速公路之间的交叉点数量。 ## 输入输出格式 输入格式 输入文件以T开头代表测试用例的数量。每个测试用例都以三个数字开始(N, M, K),接下来的K行中每一行都包含两个数字代表通过高速公路连接的城市数量。第一个是东海岸城市的数量第二个是西海岸城市的数量。 ### 样例输入 1 3 4 4 1 4 2 3 3 2 3 1 ### 样例输出 Test case 1: 5

[English](/problems/MSE06H/en/) [Vietnamese](/problems/MSE06H/vn/) Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coast and M cities on the West coast (M The funding for the construction is guaranteed by ACM. A major portion of the sum is determined by the number of crossings between superhighways. At most two superhighways cross at one location. Write a program that calculates the number of the crossings between superhighways.

The input file starts with T - the number of test cases. Each test case starts with three numbers – N, M, K. Each of the next K lines contains two numbers – the numbers of cities connected by the superhighway. The first one is the number of the city on the East coast and second one is the number of the city of the West coast.

For each test case write one line on the standard output: Test case "case number": "number of crossings"