luogu#P11484. [NordicOI 2021] Amazing Whispers

[NordicOI 2021] Amazing Whispers

题目背景

翻译自 NordicOI2021C 题。

NordicOI2021 官网,需要使用 Wayback machine 查看。

题目描述

一群人在玩游戏。在这个游戏中,一个密语会按照以下规则在一群人之间传递:

n×mn \times m 个人被分成 mm 组,每组 nn 个人。一个密语被分成 nn 个不同的消息。然后消息从第 11 组传到第 22 组,从第 22 组传到第 33 组。以此类推,直到传到组 mm,密语中的每条消息都要传递,但每个人只能知道一条消息。

为了让观察的人更难追踪到信息,组 ii 中的每个人都会假装他们在把信息传给组 i+1i+1 中的 nn 个人。这些人中,只有一个人会得到信息,其余的人都未得到。这样,观察的人就不可能知道第 i+1i+1 组中哪个人收到了信息。第 ii 组的人已经安排好了,使第 i+1i+1 组的每个人都只能得到一条消息。

当所有消息都到达第 mm 组时,它们将被大声朗读出来。所有的消息都被成功接收了,但是有一条被替换为了一个粗鲁的词。最初是第 AA 个人发送了丢失的信息,第 BB 个人大声读出了这个粗鲁的单词。你需要求出在哪里发生了替换。你不知道这个信息是如何传递的,你只知道有一些看起来在耳语的人(包括传递真实信息的人和用来迷惑你的人)。

输入格式

第一行四个整数 n,m,A,Bn,m,A,B。人的编号从 00(n×m)1(n\times m)-1。第 pp 个人在第 p/n+1\lfloor p/n \rfloor +1 组。

接下来 n×(m1)n \times (m-1) 行,每行第一个数为 kik_i,表示第 ii 个人在对多少个人耳语,接下来 kik_i 个数表示第 ii 个人分别在和谁耳语。

输出格式

第一行输出一个正整数 SS,代表可能参与替换信息的人数,接下来 SS 行分别是参与替换信息的人,编号从小到大输出。

2 3 1 5
1 3
1 2
2 5 4
2 4 5
3
1
2
5
3 3 0 6
1 4
1 5
1 3
1 7
2 6 7
1 8
3
0
4
6

提示

Subtask 分数 约束
Subtask 00 18 n=2n=2
Subtask 11 16 m=3m=3n8n \le 8
Subtask 22 19 m=3m=3
Subtask 33 47 没有特殊限制

对于 100%100\% 的数据,2n202 \le n \le 202m10002 \le m \le 1000

kik_i 的和不大于 50005000

保证输入合法。