众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。
一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 $n$ 个 $[1, m]$ 范围内的正整数。等 Alice 写完，Bob 在看到 Alice 写的纸条之后开始写他的纸条。
Alice 需要保证她写下的第 $i$ 个数在集合 $S_i$ 中，Bob 需要保证他写下的第 $i$ 个数在集合 $T_i$ 中。题目保证 $1 \le |S_i|, |T_i| \le 2$。
Alice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 $n$ 个数 $b_1, \dots, b_n$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。
即设 Alice 写下的数为 $a_1, \dots, a_n$，Bob 写下的数为 $b_1, \dots, b_n$，记 $X$ 为满足 $1 \le i \le n, a_i = b_i$ 的下标 $i$ 的个数，则 Alice 希望最大化 $X$， Bob 在保证 $b_1, \dots, 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 输出
1
样例 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_2 = 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$ 的值，她会选择第四种填法。
样例 2
见选手目录下的 game/game2.in 与 game/game2.ans。这个样例满足测试点 1 ~ 5 的条件。
样例 3
见选手目录下的 game/game3.in 与 game/game3.ans。这个样例满足测试点 6 的条件。
样例 4
见选手目录下的 game/game4.in 与 game/game4.ans。这个样例满足测试点 7 的条件。
样例 5
见选手目录下的 game/game5.in 与 game/game5.ans。这个样例满足测试点 8 的条件。
样例 6
见选手目录下的 game/game6.in 与 game/game6.ans。这个样例满足测试点 9 的条件。
样例 7
见选手目录下的 game/game7.in 与 game/game7.ans。这个样例满足测试点 10 ~ 11 的条件。
样例 8
见选手目录下的 game/game8.in 与 game/game8.ans。这个样例满足测试点 12 ~ 13 的条件。
样例 9
见选手目录下的 game/game9.in 与 game/game9.ans。这个样例满足测试点 23 ~ 25 的条件。
子任务
对于所有的数据，保证：$1 \le T \le 1000$；$1 \le n, m \le 10^6$；$1 \le |S_i|, |T_i| \le 2$；集合 $S_i, T_i$ 都是 $\{1, 2, \dots, m\}$ 的子集且集合内元素两两不同。
表格中 $\sum n, \sum m$ 分别表示同个测试点内所有测试数据的 $n$ 总和和 $m$ 总和。$\sum n^2, \sum m^2, \sum n^3, \sum m^3$ 的含义类似。
| 测试点编号 | 数据范围 | 特殊性质 |
|---|---|---|
| 1 | $T \le 20, n, m \le 10$ | |
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | $n, m \le 200, \sum n^3, \sum m^3 \le 4 \cdot 10^7$ | A |
| 7 | B | |
| 8 | C | |
| 9 | D | |
| 10 | ||
| 11 | ||
| 12 | $n, m \le 2000, \sum n^2, \sum m^2 \le 4 \cdot 10^7$ | |
| 13 | ||
| 14 | $n, m \le 1.5 \cdot 10^5, \sum n, \sum m \le 3 \cdot 10^5$ | A |
| 15 | B | |
| 16 | ||
| 17 | C | |
| 18 | ||
| 19 | D | |
| 20 | ||
| 21 | ||
| 22 | ||
| 23 | $n, m \le 10^6, \sum n, \sum m \le 1.5 \cdot 10^6$ | |
| 24 | ||
| 25 |
特殊性质 A：对于任何 $1 \le i \le n$，$S_i$ 和 $T_i$ 互不相交，即 $S_i \cap T_i = \emptyset$。 特殊性质 B：$n \ge 3$，且对于任何 $1 \le i < n$，$T_i = \{i, i + 1\}$，且 $T_n = \{n, 1\}$。 特殊性质 C：对于任何 $1 \le i \le n$，$|S_i| = 1$。 特殊性质 D：对于任何 $1 \le i \le n$，$S_i = T_i$。
说明
本题部分测试点读入规模较大，我们建议你采取效率较高的读入方式。