{"raw_statement":[{"iden":"statement","content":"众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。\n\n一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 $n$ 个 $[1,m]$ 范围内的正整数。等 Alice 写完，Bob **在看到 Alice 写的纸条之后开始写他的纸条**。\n\nAlice 需要保证她写下的第 $i$ 个数在集合 $S_{i}$ 中，Bob 需要保证他写下的第 $i$ 个数在集合 $T_{i}$ 中。**题目保证** $1 \\leq\\left|S_{i}\\right|,\\left|T_{i}\\right| \\leq 2$ 。\n\nAlice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 $n$ 个数 $b_{1}, \\ldots, b_{n}$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。\n\n即设 Alice 写下的数为 $a_{1}, \\ldots, a_{n}$，Bob 写下的数为 $b_{1}, \\ldots, b_{n}$，记 $X$ 为满足 $1 \\leq i \\leq n, a_{i}=b_{i}$ 的下标 $i$ 的个数，则\n\n- Alice 希望最大化 $X,$\n- Bob 在**保证 $b_{1}, \\ldots, b_{n}$ 互不相同的前提下**希望最小化 $X$。\n\n你首先想知道 Bob 能否保证他写下的 $n$ 个数互不相同。如果 Bob 能够做到，你想知道**在双方均采取最优策略的前提下** $X$ 的值会是多少。"},{"iden":"input","content":"**本题有多组测试数据**。\n\n输入的第一行包含一个正整数 $T$，表示测试数据组数。\n\n接下来包含 $T$ 组数据，每组数据的格式如下：\n\n第一行包含两个正整数 $n,m$，表示纸条上需要写的数的个数和数的值域。\n\n接下来 $n$ 行，每行输入的第一个整数为 $\\left|S_{i}\\right|$ 表示集合 $S_{i}$ 的元素个数，接下来输入 $\\left|S_{i}\\right|$ 个正整数描述 $S_{i}$ 中的元素。\n\n接下来 $n$ 行，每行输入的第一个整数为 $\\left|T_{i}\\right|$ 表示集合 $T_{i}$ 的元素个数，接下来输入 $\\left|T_{i}\\right|$ 个正整数描述 $T_{i}$ 中的元素。"},{"iden":"output","content":"对于每组测试数据输出一行：若 Bob 无法做到他写下的 $n$ 个数互不相同，输出 `-1`；否则输出在双方均予取最优策略的前提下 $X$ 的值。"},{"iden":"note","content":"**【样例 1 解释】**\n\n在这组样例中，$S_{1}=\\{3\\}, S_{2}=T_{1}=\\{1,2\\}, S_{3}=T_{3}=\\{3,4\\}, T_{2}=\\{2,3\\}$。Alice 的填法有 $4$ 种，列举如下：\n\n第一种：$a_{1}=3,a_{2}=1,a_{3}=3$。\n\n第二种：$a_{1}=3,a_{2}=1,a_{3}=4$。\n\n第三种：$a_{1}=3,a_{2}=2,a_{3}=3$。\n\n第四种：$a_{1}=3,a_{2}=2,a_{3}=4$。\n\n由于 Bob 必须保证他所填的数互不相同，所以他有以下填法:\n\n第一种：$b_{1}=1,b_{2}=2,b_{3}=3$。\n\n第二种：$b_{1}=2,b_{3}=3,b_{3}=4$。\n\n第三种：$b_{1}=1,b_{2}=2,b_{3}=4$。\n\n第四种：$b_{1}=1,b_{2}=3,b_{3}=4$。\n\n若 Alice 选择第一种填法，则 Bob 为最小化 $X$，选择第二种填法，得到 $X=0$。\n\n若 Alice 选择第二种填法，则 Bob 为最小化 $X$，选择第一种填法，得到 $X=0$。\n\n若 Alice 选择第三种填法，则 Bob 为最小化 $X$，选择第一种填法，得到 $X=0$。\n\n若 Alice 选择第四种填法，则 Bob 无论选择哪种填法，$X$ 均不小于 $1$。\n\n因此，Alice 为最大化 $X$ 的值，她会选择第四种填法。\n\n**【子任务】**\n\n表格中 $\\sum n,\\sum m$ 分别表示同个测试点内所有测试数据的 $n$ 总和和 $m$ 总和。 $\\sum n^{2}, \\sum m^{2}, \\sum n^{3}, \\sum m^{3}$ 的含义类似。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/nbt12df0.png)\n\n特殊性质 A：对于任何 $1 \\leq i \\leq n,S_i$ 和 $T_i$ 互不相交，即 $S_i \\cap T_i=\\emptyset$。\n\n特殊性质 B：$n \\geq 3$，且对于任何 $1 \\leq i<n, T_{1} =\\{i,i+1\\}$，且 $T_{n}=\\{n,1\\}$。\n\n特殊性质 C：对于任何 $1 \\leq i \\leq n,|S_i|=1$。\n\n特殊性质 D：对于任何 $1 \\leq i \\leq n,S_{i}=T_{i}$。\n\n**【提示】**\n\n本题部分测试点读入规模较大，我们建议你采取效率较高的读入方式。"}],"translated_statement":null,"sample_group":[["1\n3 4\n1 3\n2 1 2\n2 3 4\n2 1 2\n2 2 3\n2 3 4\n","1\n"],["见附件中的 game/game2.in","见附件中的 game/game2.ans"],["见附件中的 game/game3.in","见附件中的 game/game3.ans"],["见附件中的 game/game4.in","见附件中的 game/game4.ans"],["见附件中的 game/game5.in","见附件中的 game/game5.ans"],["见附件中的 game/game6.in","见附件中的 game/game6.ans"],["见附件中的 game/game7.in","见附件中的 game/game7.ans"],["见附件中的 game/game8.in","见附件中的 game/game8.ans"],["见附件中的 game/game9.in","见附件中的 game/game9.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}