← 返回题目列表

Codeforces · 1475/C

C. 贝尔兰的球

中文机器翻译题面 查看原题

Vasya就读的学校正在筹备毕业典礼。计划的表演之一是一场舞会,由一对男孩和女孩参加。

每个班级必须在舞会上表演两对情侣。在 Vasya 的班级中,$$$a$$$ 男生和 $$$b$$$ 女生希望参加。但并非所有男孩和女孩都准备好双人跳舞。

正式来说,你知道 $$$k$$$ 可能的一男一女对。您需要选择其中两对,以便没有人出现在超过一对中。

例如,如果 $$$a=3$$$、$$$b=4$$$、$$$k=4$$$ 和情侣 $$$(1, 2)$$$、$$$(1, 3)$$$、$$$(2, 2)$$$、$$$(3, 4)$$$ 准备一起跳舞(在每一对中,男孩的号码排在第一位,然后是女孩的号码),那么以下两对的组合是可能的(下面并未列出所有可能的选项):

- $$$(1, 3)$$$ 和 $$$(2, 2)$$$;
- $$$(3, 4)$$$ 和 $$$(1, 3)$$$;

但以下组合是不可能的:

- $$$(1, 3)$$$ 和 $$$(1, 2)$$$ - 第一个男孩进入两对;
- $$$(1, 2)$$$ 和 $$$(2, 2)$$$ - 第二个女孩进入两对;

找出选择符合上述条件的两对的方法数。如果两条路由不同的对组成,则认为它们是不同的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le a, b, k \le 2 \cdot 10^5$$$) - 班级中男孩和女孩的数量以及准备一起跳舞的情侣数量。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots a_k$$$。 ($$$1 \le a_i \le a$$$),其中 $$$a_i$$$ 是编号为 $$$i$$$ 的配对中男孩的编号。

每个测试用例的第三行包含 $$$k$$$ 整数 $$$b_1, b_2, \ldots b_k$$$。 ($$$1 \le b_i \le b$$$),其中 $$$b_i$$$ 是编号为 $$$i$$$ 的配对中女孩的编号。

保证所有测试用例的 $$$a$$$、$$$b$$$ 和 $$$k$$$ 之和不超过 $$$2 \cdot 10^5$$$。

保证每一对在一个测试用例中最多指定一次。

输出

对于每个测试用例,在单独的行上打印一个整数 - 选择符合上述条件的两对的方法数。

示例

输入 #1

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

输出 #1

4
0
2

注意

在第一个测试用例中,以下配对组合适合:

- $$$(1, 2)$$$ 和 $$$(3, 4)$$$;
- $$$(1, 3)$$$ 和 $$$(2, 2)$$$;
- $$$(1, 3)$$$ 和 $$$(3, 4)$$$;
- $$$(2, 2)$$$ 和 $$$(3, 4)$$$。

第二个测试用例中只有一对。

在第三个测试用例中,以下配对组合适合:

- $$$(1, 1)$$$ 和 $$$(2, 2)$$$;
- $$$(1, 2)$$$ 和 $$$(2, 1)$$$。