9552 - 填数游戏

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

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

Alice 需要保证她写下的第 i 个数在集合 $S{i} 中，Bob 需要保证他写下的第 i 个数在集合 T{i}$ 中。题目保证 $1 \leq\left|S{i}\right|,\left|T{i}\right| \leq 2$ 。

Alice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 n 个数 $b{1}, \ldots, b{n}$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。

即设 Alice 写下的数为 $a{1}, \ldots, a{n}，Bob 写下的数为 b{1}, \ldots, b{n}，记 X 为满足 1 \leq i \leq n, a{i}=b{i} 的下标 i$ 的个数，则

• Alice 希望最大化 X,
• Bob 在保证 $b{1}, \ldots, b{n}$ 互不相同的前提下希望最小化 X。

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

本题有多组测试数据。

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

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

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

接下来 n 行，每行输入的第一个整数为 $\left|S{i}\right| 表示集合 S{i} 的元素个数，接下来输入 \left|S{i}\right| 个正整数描述 S{i}$ 中的元素。

接下来 n 行，每行输入的第一个整数为 $\left|T{i}\right| 表示集合 T{i} 的元素个数，接下来输入 \left|T{i}\right| 个正整数描述 T{i}$ 中的元素。

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

【样例 1 解释】

在这组样例中，$S{1}={3}, S{2}=T{1}={1,2}, S{3}=T{3}={3,4}, T{2}={2,3}。Alice 的填法有 4$ 种，列举如下：

第一种：$a{1}=3,a{2}=1,a_{3}=3$。

第二种：$a{1}=3,a{2}=1,a_{3}=4$。

第三种：$a{1}=3,a{2}=2,a_{3}=3$。

第四种：$a{1}=3,a{2}=2,a_{3}=4$。

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

第一种：$b{1}=1,b{2}=2,b_{3}=3$。

第二种：$b{1}=2,b{3}=3,b_{3}=4$。

第三种：$b{1}=1,b{2}=2,b_{3}=4$。

第四种：$b{1}=1,b{2}=3,b_{3}=4$。

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

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

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

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

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

【子任务】

表格中 \sum n,\sum m 分别表示同个测试点内所有测试数据的 n 总和和 m 总和。 \sum n^{2}, \sum m^{2}, \sum n^{3}, \sum m^{3} 的含义类似。

特殊性质 A：对于任何 1 \leq i \leq n,S_i 和 T_i 互不相交，即 S_i \cap T_i=\emptyset。

特殊性质 B：n \geq 3，且对于任何 $1 \leq i<n, T{1} ={i,i+1}，且 T{n}={n,1}$。

特殊性质 C：对于任何 1 \leq i \leq n,|S_i|=1。

特殊性质 D：对于任何 $1 \leq i \leq n,S{i}=T{i}$。

联合省选