A6637 · 「联合省选 2023」填数游戏

题目描述

众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。 一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 $n$ 个 $[1,m]$ 范围内的正整数。等 Alice 写完，Bob **在看到 Alice 写的纸条之后开始写他的纸条**。 Alice 需要保证她写下的第 $i$ 个数在集合 $S_{i}$ 中，Bob 需要保证他写下的第 $i$ 个数在集合 $T_{i}$ 中。**题目保证** $1 \leq\left|S_{i}\right|,\left|T_{i}\right| \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$ 行，每行输入的第一个整数为 $\left|S_{i}\right|$ 表示集合 $S_{i}$ 的元素个数，接下来输入 $\left|S_{i}\right|$ 个正整数描述 $S_{i}$ 中的元素。 接下来 $n$ 行，每行输入的第一个整数为 $\left|T_{i}\right|$ 表示集合 $T_{i}$ 的元素个数，接下来输入 $\left|T_{i}\right|$ 个正整数描述 $T_{i}$ 中的元素。

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

输入 #1

输出 #1