P0542

Pku3915 Black Vienna

Pku3915 Black Vienna

本题基于桌面游戏 Black Vienna。游戏中有三名玩家和 1818 张牌，分别标记为 AA 到 RR。其中 33 张牌被抽出并藏起来，组成「Black Vienna」团伙；剩下的牌洗混后发给三名玩家，每人 55 张。玩家之间从不互相展示手牌。

另有一叠「质询牌」，每张上写着三个互不相同、按字母升序排列的字母，例如 ACG 或 BHR。玩家按 1,2,31, 2, 3 的顺序轮流行动：轮到某名玩家时，他选出一张质询牌，正面朝上放到另一名玩家面前，被质询的玩家必须诚实地说出自己手上一共持有其中几个字母（但不说是哪几个）。所有玩家都能看到质询的结果。游戏持续到某名玩家推断出团伙的三张牌为止。

例如，假设手牌的分配与之后的过程如下：

玩家 1：DGJLP    玩家 2：EFOQR    玩家 3：ACHMN    团伙：BIK

第 1 轮：玩家 1 用 BJK 质询玩家 2，回答 0
第 2 轮：玩家 2 用 ABK 质询玩家 3，回答 1
第 3 轮：玩家 3 用 DEF 质询玩家 2，回答 2
第 4 轮：玩家 1 用 EIL 质询玩家 2，回答 1
第 5 轮：玩家 2 用 FIP 质询玩家 3，回答 0
第 6 轮：玩家 3 用 GMO 质询玩家 1，回答 1
第 7 轮：玩家 1 用 OQR 质询玩家 2，回答 3
第 8 轮：玩家 2 用 ADQ 质询玩家 3，回答 1
第 9 轮：玩家 3 用 EGJ 质询玩家 1，回答 2

事实上这局游戏并不需要进行到第 99 轮：经过充分的推理，玩家 11 在第 88 轮之后就能断定团伙是 BIK。

你的任务是分析若干局游戏的记录，求出最早在哪一轮之后可以确定团伙的三张牌。

输入格式

输入包含 11 到 1212 组数据，最后一行只有一个 00。

每组数据的第一行是记录的轮数 tt。

第二行是四个用空格分隔的字符串，依次为玩家 11、22、33 的手牌以及团伙的牌。

接下来 tt 行按顺序描述每一轮，每行三个用空格分隔的部分：被质询玩家的编号、质询的字母串、给出的回答。

所有字母串只包含 AA 到 RR 的大写字母，且严格按字母升序排列。同一个质询串可能在一局中出现多次。

输出格式

每组数据输出一行。如果列出的所有轮次结束后仍没有玩家能确定团伙，输出一个字符 ?；如果有玩家能确定团伙，输出最早的轮次编号，表示在这一轮之后至少有一名玩家能确定答案。

样例输入

9
DGJLP EFOQR ACHMN BIK
2 BJK 0
3 ABK 1
2 DEF 2
2 EIL 1
3 FIP 0
1 GMO 1
2 OQR 3
3 ADQ 1
1 EGJ 2
3
ABCDE FGHIJ KLMNO PQR
3 BKQ 1
1 ADE 3
2 CHJ 2
0

样例输出

8
?

样例解释

以第一组数据为例，站在玩家 11（手牌 DGJLP）的角度推理：

  • 第 11 轮 2 BJK 0：玩家 22 手上没有 B、J、K；
  • 第 22 轮 3 ABK 1：玩家 33 的 A、B、K 中恰有一张；
  • 第 33 轮 2 DEF 2：D 在玩家 11 手上，所以玩家 22 持有 E 和 F，于是玩家 33 没有 E、F；
  • 第 44 轮 2 EIL 1：玩家 22 已知持有 E，所以他没有 I、L；
  • 第 55 轮 3 FIP 0：玩家 33 没有 F、I、P；
  • 第 66 轮 1 GMO 1：质询的是玩家 11 自己，对他没有新信息；
  • 第 77 轮 2 OQR 3：玩家 22 持有 O、Q、R，于是玩家 33 没有这三张；
  • 第 88 轮 3 ADQ 1：玩家 33 没有 D（在玩家 11 手上）、也没有 Q（在玩家 22 手上），所以他持有 A；结合第 22 轮的「A、B、K 中恰有一张」，可知玩家 33 没有 B、K。

此时玩家 11 知道自己和玩家 22、玩家 33 都不持有 B、I、K，因此隐藏的三张牌就是 BIK，答案为 88。从玩家 22、33 的角度同样推理，在前 88 轮内都无法更早得出结论。

第二组数据中，所有轮次结束后仍没有人能确定团伙，因此输出 ?。

数据范围

  • 输入包含 11 到 1212 组数据；
  • 2≤t≤152\le t\le 15。

来源与许可

本题为 PKU 3915 试题「Black Vienna」，题面与测试数据整理自 BZOJ 2484。

样例 1

输入

9
DGJLP EFOQR ACHMN BIK
2 BJK 0
3 ABK 1
2 DEF 2
2 EIL 1
3 FIP 0
1 GMO 1
2 OQR 3
3 ADQ 1
1 EGJ 2
3
ABCDE FGHIJ KLMNO PQR
3 BKQ 1
1 ADE 3
2 CHJ 2
0

输出

8
?