#NOISX2023E. [NOI 2023 联合省选] 填数游戏

[NOI 2023 联合省选] 填数游戏

题目描述

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

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

Alice\texttt{Alice} 需要保证她写下的第 ii 个数在集合 Si\mathrm{S}_{i} 中,Bob\texttt{Bob} 需要保证他写下的第 ii 个数在集合 Ti\mathrm{T}_{i} 中。题目保证 1Si,Ti21 \leq\left|\mathrm{S}_{i}\right|,\left|\mathrm{T}_{i}\right| \leq 2

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

即设 Alice\texttt{Alice} 写下的数为 a1,ana_{1}, \cdots,a_{n}Bob\texttt{Bob} 写下的数为 b1,bnb_{1}, \cdots,b_{n},记 XX 为满足 11 \leq inai=bii \leq n,a_{i}=b_{i} 的下标 ii 的个数,则

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

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

输入格式

本题有多组测试数据。

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

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

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

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

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

输出格式

对于每组测试数据输出一行:若 Bob\texttt{Bob} 无法做到他写下的 nn 个数互不相同,输出 -1 ;

否则输出在双方均予取最优策略的前提下 XX 的值。

样例 #1

样例输入 #1

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

样例输出 #1

1

提示

样例解释

【样例 1 解释】

在这组样例中,S1={3},S2=T1={1,2},S3=T3={3,4},T2={2,3}\mathrm{S}_{1}=\{3\}, \mathrm{S}_{2}=\mathrm{T}_{1}=\{1,2\}, \mathrm{S}_{3}=\mathrm{T}_{3}=\{3,4\}, \mathrm{T}_{2}=\{2,3\}

Alice\texttt{Alice} 的填法有 4 种,列举如下:

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

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

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

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

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

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

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

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

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

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

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

Alice\texttt{Alice} 选择第四种填法,则 Bob\texttt{Bob} 无论选择哪种填法,XX 均不小于 1。

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

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

特殊性质 A\texttt{A}:对于任何 1in1\le i\le nSi\mathrm{S}_iTi\mathrm{T}_i 互不相交,即 SiTi=\mathrm{S}_i ∩ \mathrm{T}_i=\empty

特殊性质 B\texttt{B}n3n \geq 3,且对于任侏何 1i<nTi={i,i+1}1 \le i < n,\mathrm{T}_{i}=\{i,i+1\},且 Tn={n,1}\mathrm{T}_{n}=\{n,1\}

特殊性质 C\texttt{C}:对于任何 1in,Si=11 \leq i \leq n,\left|\mathrm{S}_{i}\right|=1

特殊性质 D\texttt{D}:对于任何 1inSi=Ti1 \leq i \leq n,\mathrm{S}_{i}=\mathrm{T}_{i}

IO 提示

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