一群朋友想要玩“神奇耳语”游戏,在这个游戏中,秘密短语根据以下规则在人群中传递:
你有 $N \times M$ 个人,被分成 $M$ 个组,每组 $N$ 人。一个秘密短语被分为 $N$ 个不同的消息,第 1 组的每个成员接收一条不同的消息。随后,消息从第 1 组传到第 2 组,再从第 2 组传到第 3 组,以此类推,直到最终从第 $M-1$ 组传到第 $M$ 组。短语中的每条消息都必须被传递,但每个人最多只能听到一条消息。
为了让观察者更难追踪消息,第 $i$ 组的每个人都会表现得好像在向第 $i+1$ 组的至多 $N$ 个人耳语。实际上,只有其中一个人会听到消息——对于其余的人,发送者只是假装在耳语。这样,观察者就无法判断第 $i+1$ 组中究竟是谁收到了消息。第 $i$ 组的人已经安排好,使得第 $i+1$ 组的每个人都能恰好听到一条消息。
当所有消息到达第 $M$ 组时,它们会被大声读出。结果发现,除了其中一条消息被替换成了一个粗鲁的词汇外,其余消息都已成功接收。人 $A$ 最初持有那条丢失的消息,而人 $B$ 是最终大声读出那个粗鲁词汇的人。你不知道替换是在哪个阶段发生的。谁可能是这场恶作剧的始作俑者?你不知道消息是如何传递的,你只知道哪些人之间表现出了耳语的行为。
输入格式
第一行包含四个整数 $N, M, A, B$,如题目所述。 人的编号从 $0$ 到 $(N \times M) - 1$,其中人 $p$ 属于第 $\lfloor p/N \rfloor + 1$ 组。($\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。)
接下来有 $N \times (M - 1)$ 行。第 $i$ 行描述了第 $i$ 个人表现出向谁耳语。 每行以一个数字 $K_i$ 开头,表示第 $i$ 个人表现出向其耳语的人数。随后是 $K_i$ 个整数 $R_{i,0} \dots R_{i,K_i-1}$,指定了这些人是谁。由于这些人总是属于第 $i$ 个人所在组的下一组,这些数字满足 $R_{i,j}/N = i/N + 1$。
输出格式
第一行输出一个整数 $S$,表示可能是恶作剧始作俑者的人数。接下来的 $S$ 行应列出这些人,每行一人,按编号升序排列。
数据范围
$2 \le N \le 20$ $2 \le M \le 1\,000$ 所有 $K_i$ 的总和不超过 $5\,000$ 输入描述了一种有效的耳语执行方式。
| 子任务 | 分值 | 附加约束 |
|---|---|---|
| 子任务 1 | 18 | $N = 2$ |
| 子任务 2 | 16 | $M = 3; N \le 8$ |
| 子任务 3 | 19 | $M = 3$ |
| 子任务 4 | 47 | 无附加约束 |
样例
输入 1
2 3 1 5 1 3 1 2 2 5 4 2 4 5
输出 1
3 1 2 5
输入 2
3 3 0 6 1 4 1 5 1 3 1 7 2 6 7 1 8
输出 2
3 0 4 6