P7352 炉心融解

2020-2021 国家集训队自选题

你叫了 $n$ 个人来玩游戏。$n$ 个人从 $0$ 到 $n-1$ 编号，按顺序坐成一圈，$0$ 号与 $n-1$ 号相邻。 你给这 $n$ 个人每人发了一张写着数字 $\texttt{0}$ 或 $\texttt{1}$ 的卡片。每个人都可以看到**除了相邻的两个人以外**所有人的卡片数字，也可以看到自己的。 游戏共进行 $m$ 回合。第 $i$ 回合你会向所有人公布 $k_i$ 条信息，信息的格式都是“某个集合里存在某种数字的卡片”。公布完之后： - 如果某个人手里的卡片写着 $\texttt 0$，且他可以通过推断确定相邻的两个人卡片数字**逻辑或**的值，他就必须大喊“Meltdown！”。 - 如果某个人手里的卡片写着 $\texttt 1$，且他可以通过推断确定相邻的两个人卡片数字**逻辑异或**的值，他就必须大喊“Meltdown！”。 所有人都清楚游戏规则，且都有极强的推断能力，只要依据他已有的信息能够推断出来他就必须要喊。喊话是所有人同时喊，不可以听别人喊完了再继续推断。然后本回合结束，进入下一回合。 除此之外这 $n$ 个人没有任何信息交流。现在给出每个人的卡片数字和你公布的所有信息，求每个人第一次喊出“Meltdown！”是在第几回合。

输入的第一行包括两个正整数 $n,m$，表示人数和回合数。第二行 $n$ 个整数，分别表示编号 $0$ 到 $n-1$ 的人的卡片上的数字。接下来包括 $m$ 个部分，第 $i$ 部分描述了第 $i$ 回合你公布的信息。 第 $i$ 部分的第一行包括一个非负整数 $k_i$，表示第 $i$ 回合公布的信息条数。接下来 $k_i$ 行，每行第一个正整数 $p$，表示集合的人数，接下来 $p$ 个互不相同的整数表示集合里所有人的编号。最后一个整数 $c$，表示这个集合里存在数字为 $c$ 的卡片。数据保证这些信息是正确的。

输出包括一行 $n$ 个整数，分别表示编号 $0$ 到 $n-1$ 的人第一次喊出“Meltdown！”时的回合数。如果他自始自终都没有喊“Meltdown！”，这个数输出 $-1$。

对于 $100\%$ 的数据，$3\le n\le 16$，$\ 1\le m\le 100$，$0\le \sum k\le 2\times 10^3$。