← 返回题目列表

Codeforces · 2141/B

B. 游戏

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

Alice 和 Bob 计划一起玩一款在线游戏,但尚未决定玩哪一个。 Alice 列出了她喜欢的 $$$n$$$ 游戏:$$$a_1、a_2、\dots、a_n$$$。另一方面,鲍勃有一个他喜欢的 $$$m$$$ 游戏列表:$$$b_1、b_2、\dots、b_m$$$。他们的列表中至少有一款共同的游戏。

为了选择游戏,他们轮流从列表中推荐游戏。爱丽丝首先推荐了她最喜欢的游戏之一。如果鲍勃喜欢,他们就会玩那个游戏。如果没有,鲍勃会推荐他最喜欢的游戏之一。如果爱丽丝喜欢,他们就会玩那个游戏。这个交替过程继续进行,爱丽丝和鲍勃各自轮流从他们的列表中推荐游戏,确保没有游戏被推荐超过一次。

你的任务是计算 最大可能 他们在选择玩哪个游戏时会提出的建议数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 100$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1 \lt a_2 \lt \cdots \lt a_n$$$ ($$$1 \le a_i \le 100$$$)。

第三行包含 $$$m$$$ 整数 $$$b_1 \lt b_2 \lt \cdots \lt b_m$$$ ($$$1 \le b_i \le 100$$$)。

数组 $$$a$$$ 和 $$$b$$$ 至少包含一个公共整数。

输出

对于每个测试用例,打印一个整数 - 最大可能 他们在选择玩哪个游戏时会提出的建议数量。

示例

输入
复制

3
2 3
1 2
2 3 5
1 1
5
5
4 2
1 3 4 7
4 6

输出
复制

3
1
4

注意

在第一个测试用例中,建议的最大数量为 $$$3$$$。其实现如下:

  • Alice 建议游戏 $$$1$$$,但 Bob 不喜欢;
  • Bob 建议游戏 $$$5$$$,但 Alice 不喜欢;
  • Alice 推荐了 Bob 喜欢的游戏 $$$2$$$,然后他们就去玩那个游戏。

在第二个测试用例中,Alice 只能推荐 Bob 喜欢的游戏 $$$5$$$,所以他们会立即去玩。

在第三个测试用例中,建议的最大数量为$$$4$$$。其实现如下:

  • Alice 建议游戏 $$$7$$$,但 Bob 不喜欢;
  • Bob 建议游戏 $$$6$$$,但 Alice 不喜欢;
  • Alice 建议游戏 $$$1$$$,但 Bob 不喜欢;
  • Bob 推荐了 Alice 喜欢的游戏 $$$4$$$,然后他们就去玩了。