← 返回题目列表

Codeforces · 1453/A

A. 取消火车

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

Gildong 镇有一个火车系统,有从底端到顶端的 $$$100$$$ 火车和从左端到右端的 $$$100$$$ 火车。两侧出发的列车编号分别为$$$1$$$至$$$100$$$,所有列车速度相同。我们来看一下下面的图片。

列车系统可以表示为 2D 平面上的坐标。从底端出发的第 $$$i$$$ 列车最初位于 $$$(i,0)$$$,并将在 $$$T$$$ 分钟后到达 $$$(i,T)$$$,从左端出发的第 $$$i$$$ 列车最初位于 $$$(0,i)$$$,并将在 $$$T$$$ 分钟后到达 $$$(T,i)$$$。所有列车均在 $$$101$$$ 分钟后抵达目的地。

然而,Gildong发现一些预定在特定时间同时出发的火车非常危险。此时,$$$n$$$ 趟列车计划从底端出发,$$$m$$$ 趟列车计划从左端出发。如果两列火车同时在 $$$(x,y)$$$ 处,对于某些 $$$x$$$ 和 $$$y$$$,它们将会相撞。因此,他要求您找出应该取消的最少火车数量,以防止所有此类事故的发生。

输入

每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。

每个测试用例包含三行。每个测试用例的第一行由两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 100$$$) 组成 - 分别是计划从底端出发的火车数量和计划从左端出发的火车数量。

每个测试用例的第二行包含 $$$n$$$ 整数。每个整数是一个预定从底端开始的列车编号。这些数字严格按递增顺序给出,并且介于 $$$1$$$ 和 $$$100$$$(含)之间。

每个测试用例的第三行包含 $$$m$$$ 整数。每个整数都是一个预定从左端开始的列车编号。这些数字严格按递增顺序给出,并且介于 $$$1$$$ 和 $$$100$$$(含)之间。

输出

对于每个测试用例,打印一个整数:为了防止所有崩溃而应该取消的火车的最小数量。

示例

输入 #1

3
1 2
1
3 4
3 2
1 3 4
2 4
9 14
2 7 16 28 33 57 59 86 99
3 9 14 19 25 26 28 35 41 59 85 87 99 100

输出 #1

0
1
3

注意

在第一种情况下,我们可以证明如果遵循当前的时间表就不会发生崩溃。因此,答案是零。

第二种情况,在$$$T=4$$$时,会发生崩溃,如下图所示。我们可以证明,取消其中一趟列车后,其余列车都不会出轨。因此,答案是一。