题目描述

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

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

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

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

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

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

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

---

输入格式

本题有多组测试数据。

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

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

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

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

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

---

输出格式

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

---

样例

样例 1

输入

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

输出

1

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

1. $a_{1}=3$, $a_{2}=1$, $a_{3}=3$
2. $a_{1}=3$, $a_{2}=1$, $a_{3}=4$
3. $a_{1}=3$, $a_{2}=2$, $a_{3}=3$
4. $a_{1}=3$, $a_{2}=2$, $a_{3}=4$

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

1. $b_{1}=1$, $b_{2}=2$, $b_{3}=3$
2. $b_{1}=2$, $b_{2}=3$, $b_{3}=4$
3. $b_{1}=1$, $b_{2}=2$, $b_{3}=4$
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$ 的值，她会选择第四种填法。

---

样例 2-9

详见附加文件。

---

数据范围与提示

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

测试点	数据范围	特殊性质
$1\sim 5$	$T\le 20$, $n,m\le 10$	无
$6\sim 11$	$n,m\le 200$, $\sum n^3,\sum m^3\le 4\cdot 10^7$	见下
$12,13$	$n,m\le 2000$, $\sum n^2,\sum m^2\le 4\cdot 10^7$	无
$14\sim 22$	$n,m\le 1.5\cdot 10^5$, $\sum n,\sum m\le 3\cdot 10^5$	见下
$23\sim 25$	$n,m\le 10^6$, $\sum n,\sum m\le 1.5\cdot 10^6$	无

特殊性质说明：

• 性质 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_{i} =\{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}$。

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