#2022. 「PTS 2023」填数游戏

众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。

一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 个 范围内的正整数。等 Alice 写完，Bob 在看到 Alice 写的纸条之后开始写他的纸条。

Alice 需要保证她写下的第 个数在集合 中，Bob 需要保证他写下的第 个数在集合 中。题目保证 。

Alice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 个数 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。

即设 Alice 写下的数为 ，Bob 写下的数为 ，记 为满足 的下标 的个数，则

• Alice 希望最大化
• Bob 在保证 互不相同的前提下希望最小化 。

你首先想知道 Bob 能否保证他写下的 个数互不相同。如果 Bob 能够做到，你想知道在双方均采取最优策略的前提下 的值会是多少。

从文件 game.in 中读取数据。

本题有多组测试数据。

输入的第一行包含一个正整数 ，表示测试数据组数。

接下来包含 组数据，每组数据的格式如下：

第一行包含两个正整数 ，表示纸条上需要写的数的个数和数的值域。

接下来 行，每行输入的第一个整数为 表示集合 的元素个数，接下来输入 个正整数描述 中的元素。

接下来 行，每行输入的第一个整数为 表示集合 的元素个数，接下来输入 个正整数描述 中的元素。

输出到文件 game.out 中。

对于每组测试数据输出一行：若 Bob 无法做到他写下的 个数互不相同，输出 -1；否则输出在双方均予取最优策略的前提下 的值。

样例 1 输入

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

样例 1 输出

1

样例 1 解释

在这组样例中，。Alice 的填法有 种，列举如下：

第一种：。

第二种：。

第三种：。

第四种：。

由于 Bob 必须保证他所填的数互不相同，所以他有以下填法:

第一种：。

第二种：。

第三种：。

第四种：。

若 Alice 选择第一种填法，则 Bob 为最小化 ，选择第二种填法，得到 。

若 Alice 选择第二种填法，则 Bob 为最小化 ，选择第一种填法，得到 。

若 Alice 选择第三种填法，则 Bob 为最小化 ，选择第一种填法，得到 。

若 Alice 选择第四种填法，则 Bob 无论选择哪种填法， 均不小于 。

因此，Alice 为最大化 的值，她会选择第四种填法。

样例 2

见选手目录下的 game/game2.in 与 game/game2.ans。

样例 3

见选手目录下的 game/game3.in 与 game/game3.ans。

样例 4

见选手目录下的 game/game4.in 与 game/game4.ans。

样例 5

见选手目录下的 game/game5.in 与 game/game5.ans。

样例 6

见选手目录下的 game/game6.in 与 game/game6.ans。

样例 7

见选手目录下的 game/game7.in 与 game/game7.ans。

样例 8

见选手目录下的 game/game8.in 与 game/game8.ans。

样例 9

见选手目录下的 game/game9.in 与 game/game9.ans。

表格中 分别表示同个测试点内所有测试数据的 总和和 总和。 的含义类似。

• 测试点 ：
• 测试点 ：
• 测试点 ：
• 测试点 ：
• 测试点 ：
• 测试点 具有性质 A
• 测试点 具有性质 B
• 测试点 具有性质 C
• 测试点 具有性质 D

特殊性质 A：对于任何 和 互不相交，即 。

特殊性质 B：，且对于任侏何 ，且 。

特殊性质 C：对于任何 。

特殊性质 D：对于任何 。

本题部分测试点读入规模较大，我们建议你采取效率较高的读入方式。