luogu#P11484. [NordicOI 2021] Amazing Whispers
[NordicOI 2021] Amazing Whispers
题目背景
翻译自 NordicOI2021 的 C 题。
NordicOI2021 官网,需要使用 Wayback machine 查看。
题目描述
一群人在玩游戏。在这个游戏中,一个密语会按照以下规则在一群人之间传递:
个人被分成 组,每组 个人。一个密语被分成 个不同的消息。然后消息从第 组传到第 组,从第 组传到第 组。以此类推,直到传到组 ,密语中的每条消息都要传递,但每个人只能知道一条消息。
为了让观察的人更难追踪到信息,组 中的每个人都会假装他们在把信息传给组 中的 个人。这些人中,只有一个人会得到信息,其余的人都未得到。这样,观察的人就不可能知道第 组中哪个人收到了信息。第 组的人已经安排好了,使第 组的每个人都只能得到一条消息。
当所有消息都到达第 组时,它们将被大声朗读出来。所有的消息都被成功接收了,但是有一条被替换为了一个粗鲁的词。最初是第 个人发送了丢失的信息,第 个人大声读出了这个粗鲁的单词。你需要求出在哪里发生了替换。你不知道这个信息是如何传递的,你只知道有一些看起来在耳语的人(包括传递真实信息的人和用来迷惑你的人)。
输入格式
第一行四个整数 。人的编号从 到 。第 个人在第 组。
接下来 行,每行第一个数为 ,表示第 个人在对多少个人耳语,接下来 个数表示第 个人分别在和谁耳语。
输出格式
第一行输出一个正整数 ,代表可能参与替换信息的人数,接下来 行分别是参与替换信息的人,编号从小到大输出。
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 | 18 | |
Subtask | 16 | , |
Subtask | 19 | |
Subtask | 47 | 没有特殊限制 |
对于 的数据,,。
的和不大于 。
保证输入合法。