#2490. 公路交叉数

公路交叉数

Description

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

Format

Input

输入文件以TT 为开头,表示测试用例的数量。每个测试用 例都以33个数字NMKN 、M 、K 为开头。下面KK 行中的每一行都包含两个数 字,表示由高速公路连接的城市号。第11个是东海岸的城市号,第22个是 西海岸的城市号。

Output

对每个测试用例,都单行输出“Test case xx :s s ”,xx 表示输入样例编号,ss 表示交叉数。

Samples

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

来源

POJ3067