1557: 公路交叉数

东海岸有 N 个城市，西海岸有 M 个城市（N≤1000，M≤1000）， 将建成 K 条高速公路(K<=1000000)。每个海岸的城市从北到南编号为 1,2,……每条高速公路都是直线，连接东海岸的城市和西海岸的城市。建设资金由高速公路之间的交叉数决定。两个高速公路最多在一个地方交叉。请计算高速公路之间的交叉数量。

       输入有T组测试用例(1<=T<=10)。每个测试用例都以3个数字N、M、K为开头。下面K行中的每一行都包含两个数字，表示由高速公路连接的城市号。第1个是东海岸的城市号，第2个是西海岸的城市号。

对于每个测试用例，都单行输出“case x:s”，x表示输入样例编号，s表示交叉数。

1
3 4 4
1 4
2 3
3 2
3 1

case 1:5