#P9170. [省选联考 2023] 填数游戏

[省选联考 2023] 填数游戏

题目描述

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

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

Alice 需要保证她写下的第 ii 个数在集合 SiS_{i} 中,Bob 需要保证他写下的第 ii 个数在集合 TiT_{i} 中。题目保证 1Si,Ti21 \leq\left|S_{i}\right|,\left|T_{i}\right| \leq 2

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

即设 Alice 写下的数为 a1,,ana_{1}, \ldots, a_{n},Bob 写下的数为 b1,,bnb_{1}, \ldots, b_{n},记 XX 为满足 1in,ai=bi1 \leq i \leq n, a_{i}=b_{i} 的下标 ii 的个数,则

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

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

输入格式

本题有多组测试数据

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

接下来包含 TT 组数据,每组数据的格式如下:

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

接下来 nn 行,每行输入的第一个整数为 Si\left|S_{i}\right| 表示集合 SiS_{i} 的元素个数,接下来输入 Si\left|S_{i}\right| 个正整数描述 SiS_{i} 中的元素。

接下来 nn 行,每行输入的第一个整数为 Ti\left|T_{i}\right| 表示集合 TiT_{i} 的元素个数,接下来输入 Ti\left|T_{i}\right| 个正整数描述 TiT_{i} 中的元素。

输出格式

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

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

1

见附件中的 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

提示

【样例 1 解释】

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

第一种:a1=3,a2=1,a3=3a_{1}=3,a_{2}=1,a_{3}=3

第二种:a1=3,a2=1,a3=4a_{1}=3,a_{2}=1,a_{3}=4

第三种:a1=3,a2=2,a3=3a_{1}=3,a_{2}=2,a_{3}=3

第四种:a1=3,a2=2,a3=4a_{1}=3,a_{2}=2,a_{3}=4

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

第一种:b1=1,b2=2,b3=3b_{1}=1,b_{2}=2,b_{3}=3

第二种:b1=2,b3=3,b3=4b_{1}=2,b_{3}=3,b_{3}=4

第三种:b1=1,b2=2,b3=4b_{1}=1,b_{2}=2,b_{3}=4

第四种:b1=1,b2=3,b3=4b_{1}=1,b_{2}=3,b_{3}=4

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

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

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

若 Alice 选择第四种填法,则 Bob 无论选择哪种填法,XX 均不小于 11

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

【子任务】

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

特殊性质 A:对于任何 1in,Si1 \leq i \leq n,S_iTiT_i 互不相交,即 SiTi=S_i \cap T_i=\emptyset

特殊性质 B:n3n \geq 3,且对于任何 1i<n,T1={i,i+1}1 \leq i<n, T_{1} =\{i,i+1\},且 Tn={n,1}T_{n}=\{n,1\}

特殊性质 C:对于任何 1in,Si=11 \leq i \leq n,|S_i|=1

特殊性质 D:对于任何 1in,Si=Ti1 \leq i \leq n,S_{i}=T_{i}

【提示】

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