1974. 公路交叉

【题目描述】

东海岸有$n$个城市，西海岸有$m$个城市，即将建成$k$条高速公路。

每个海岸城市从北到南编号为$1,2,\cdots$，每条高速公路都是直线，分别连接东海岸和西海岸的城市。

建设资金由告诉公路之间的交叉数决定，两条高速公路最多在一个地方交叉，请你计算高速公路之间的交叉数量。

【输入格式】

输入包含多组测试数据。

第一行一个整数$T$，表示测试用例的数量。

对于每个测试用例，第$1$行三个整数$n,m,k$。

接下来$k$行，每行两个整数$x,y$，表示高速公路连接的城市号，$x$是东海岸的城市号，$y$是西海岸的城市号。

【输出格式】

对于每个测试用例，输出一行Test case id: ans，其中$id$表示测试用例编号(从$1$开始)，$ans$表示答案。

【样例输入】

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

【样例输出】

Test case 1: 5

【数据规模与约定】

$1\leq n,m\leq 1000,T\leq 10$。