Description

你拥有一家棒棒糖店。在一天开始时，你制作了 $N$ 根棒棒糖，每根棒棒糖都有唯一的口味，比如越橘、樱桃或青柠。当天会有 $N$ 位顾客依次进入你的店铺。每位顾客会给你一份他们喜欢的棒棒糖口味列表。你可以卖给他们其中任意一种他们喜欢的口味的棒棒糖，只要这种口味的棒棒糖还没有在当天卖给其他人（因为每种口味只有一根棒棒糖）。如果他们喜欢的所有口味都已经卖完了，你就不能卖棒棒糖给他们，他们会失望地离开你的店。

你在顾客到来之前并不知道他们的口味偏好。每位顾客会随机决定是否喜欢每种口味，这一决定与他们是否喜欢其他口味、以及其他人喜欢什么口味都无关。然而，你的市场调研显示，有些口味被喜欢的概率更高！例如，青柠口味被某位顾客喜欢的概率可能是 $10\%$，而樱桃口味可能只有 $1\%$。这些概率值总是独立且均匀地从区间 $[0.005, 0.1]$ 中随机选取。

显然，你希望能卖出尽可能多的棒棒糖！但由于你事先不知道顾客的口味偏好，因此你无法总是做出最优决策——有时你可能会把某种口味卖给一位顾客，之后又希望当时卖给他们另一种口味。

假设你能提前知道所有顾客的偏好并做好规划，那么你最多能卖出 $M$ 根棒棒糖。虽然你无法提前知道顾客的偏好，但本题要求你在每组输入中，卖出的棒棒糖数量至少达到 $M$ 的 $90\%$。

交互协议

本题为交互题，这意味着输入输出方式与标准题目不同。你需要与一个独立的进程进行交互，该进程既向你提供信息，也会评判你的回答。所有信息都通过标准输入进入你的程序；你需要传递的信息应通过标准输出输出。请注意，许多编程语言默认会缓冲输出，因此请确保你的输出实际被发送出去（例如，通过刷新缓冲区），再等待下一步输入。详见 FAQ 关于刷新缓冲区的说明。你通过标准错误输出的内容会被忽略，但可能会占用内存并计入内存限制，因此请勿输出过多内容。

最初，你的程序应读取一行，包含一个整数 $\mathbf{T}$，表示测试用例的数量。然后，你需要处理 $\mathbf{T}$ 组测试数据。

对于每组测试数据，你的程序应读取一行，包含一个整数 $\mathbf{N}$，表示棒棒糖的数量（也等于顾客数量）。

接下来，对于每位顾客，你的程序应读取一行，包含若干用空格分隔的整数。第一个整数为 $\mathbf{D}$，表示该顾客喜欢的口味数量。接下来有 $\mathbf{D}$ 个整数，表示这些口味的编号，严格递增。口味编号唯一，范围为 $[0, \mathbf{N} - 1]$。注意，有些顾客的 $\mathbf{D}$ 可能为零。

在每一行顾客信息后，你的程序必须输出一行，包含一个整数，表示你卖给该顾客的口味编号（必须是他们喜欢且尚未卖出的口味），或者输出 $-1$ 表示不卖棒棒糖给该顾客。在每组测试数据的第 $\mathbf{N}$ 行输出后，如果这是最后一组测试数据，程序应终止；否则，继续读取下一组测试数据。

如果你的程序出现错误（例如，尝试卖出已经卖掉的口味，或者卖给顾客他们不喜欢的口味，或者输出格式错误，或者输出超出范围的值），评测机会向你的输入流发送 $-1$，并且不会再发送其他输出。如果你的程序在收到 $-1$ 后仍然等待评测机输入，则会超时，导致超时错误。请注意，程序应自行及时退出，以获得正确的判题结果（如 Wrong Answer、Runtime Error 等），而不是超时。如果总时间或内存超限，或程序运行时出错，也会得到相应的判题结果。如果某组测试数据卖出的棒棒糖数量不足，不会导致收到 $-1$。

在处理完所有测试数据后，不要再向评测机输出任何内容。换句话说，如果你的程序在最后一组测试数据后仍然输出内容，将会被判为 Wrong Answer。

你可以使用本地测试工具进行测试。要在本地测试，你需要让测试工具与你的代码并行运行；可以使用我们的 interactive runner。更多信息请阅读该文件中的注释说明。

测试工具的使用说明已包含在工具的注释中。我们鼓励你添加自己的测试用例。请注意，虽然测试工具旨在模拟评测系统，但它不是真实的评测系统，行为可能有所不同。

关于评测机行为的说明

在每组测试数据开始时，评测机会确定所有顾客的偏好。即，对于每种口味，评测机会生成一个（隐藏的）概率列表 $P_i$，每个 $P_i$ 取值在 $[0.005, 0.1]$ 之间；每位顾客喜欢第 $i$ 种口味的概率为 $P_i$。也就是说，顾客 $j$ 是否喜欢口味 $i$ 的随机变量是独立同分布的。这些偏好在整个测试过程中保持不变，不会因你的选择而改变。

测试点 1（29 分，公开）

• $\mathbf{T} = 50$。
• $\mathbf{N} = 200$。
• $0 \leqslant \mathbf{D} \leqslant \mathbf{N}$。

Input Format

见交互协议。

Output Format

见交互协议。

Hint

请注意，以下样例交互中的 $\mathbf T$ 和 $\mathbf N$ 都比真实数据要小。用于本地测试的工具也使用更小的样例。

  t = readline_int()           // 读取 t，值为 10
  n = readline_int()           // 读取 n，值为 4（4 位顾客和 4 种口味）
  prefs = readline_int_list()  // 读取 1 2（顾客只喜欢口味 2）
  printline 2 to stdout        // 卖给该顾客口味 2
  flush stdout
  prefs = readline_int_list()  // 读取 0（顾客什么都不喜欢）
  printline -1 to stdout       // 没有可卖的口味！
  flush stdout
  prefs = readline_int_list()  // 读取 1 2（顾客只喜欢口味 2）
  printline -1 to stdout       // 口味 2 已经卖出，无法再卖
  flush stdout
  prefs = readline_int_list()  // 读取 2 1 3（顾客喜欢 1 和 3）
  printline 3 to stdout        // 注意：也可以卖 1
  flush stdout
  n = readline_int()           // （第二组数据开始）读取 1
  prefs = readline_int_list()  // 读取 1 0
  printline -1 to stdout       // 非最优但合法的选择
  flush stdout
  n = readline_int()           // （第三组数据开始）读取 5
  prefs = readline_int_list()  // 读取 2 1 3
  printline 1 to stdout
  flush stdout
  prefs = readline_int_list()  // 读取 2 1 2
  printline 1 to stdout        // 错误——尝试重复卖出同一口味！
  flush stdout
  prefs = readline_int_list()  // 读取 -1（评测机放弃评测）
  exit                         // 退出，避免超时

上述伪代码演示了如下场景：

• 第一组数据，程序共卖出两根棒棒糖。无法卖出更多，因此实际卖出数量肯定至少为最大可能数量的 $90\%$。
• 第二组数据，程序（仅为演示）选择不卖棒棒糖，虽然本可以卖。实际卖出 0 根，最大可卖 1 根。因此该组数据无法通过测试，但不会导致评测机停止输入。
• 第三组数据，程序出现错误（同样仅为演示），导致评测机停止输入。程序识别到这一点并终止。用户会看到 Wrong Answer 判定。

输入格式

见交互协议。

输出格式

见交互协议。

提示

请注意，以下样例交互中的 $\mathbf T$ 和 $\mathbf N$ 都比真实数据要小。用于本地测试的工具也使用更小的样例。

由 ChatGPT 4.1 翻译