#P15536. [nordic2021]Amazing Whispers

[nordic2021]Amazing Whispers

题目描述

一群朋友想玩一个叫做 Amazing Whispers 的游戏。秘密短语会按照如下规则在若干人之间传递。

共有 N×MN\times M 个人,分成 MM 组,每组 NN 人。秘密短语被分成 NN 条互不相同的信息,第 11 组中的每个人一开始各收到一条不同的信息。

信息从第 11 组传到第 22 组,再从第 22 组传到第 33 组,依次传递,最后从第 M1M-1 组传到第 MM 组。每条信息都必须被传递,并且每个人最多只能真正听到一条信息。

为了让旁观者更难追踪信息,每个第 ii 组的人会假装向第 i+1i+1 组中的若干人悄悄说话,但其中只有一个人真正听到了信息,其余人只是被假装传话。第 ii 组的人已经安排好,使得第 i+1i+1 组中的每个人都恰好真正听到一条信息。

当所有信息到达第 MM 组后,人们将信息读出。结果发现,除了其中一条信息被替换成了粗鲁的话之外,其余信息都成功传达。已知编号为 AA 的人一开始持有丢失的信息,编号为 BB 的人最后读出了粗鲁的话。你不知道替换发生在哪一阶段,也不知道真实信息具体是如何传递的,只知道每个人假装向哪些人传过话。

请判断哪些人有可能是这次恶作剧的实施者。

输入格式

第一行包含四个整数 N,M,A,BN,M,A,B

人员编号从 00N×M1N\times M-1。编号为 pp 的人属于第 p/N+1\left\lfloor p/N\right\rfloor+1 组。

接下来有 N×(M1)N\times(M-1) 行,第 ii 行描述编号为 ii 的人假装向哪些人悄悄说话。

每行先包含一个整数 KiK_i,表示编号为 ii 的人假装传话的人数;随后包含 KiK_i 个整数 Ri,0,Ri,1,,Ri,Ki1R_{i,0},R_{i,1},\ldots,R_{i,K_i-1},表示这些人编号。它们都属于编号 ii 所在组的下一组。

输出格式

第一行输出一个整数 SS,表示可能实施恶作剧的人数。

接下来 SS 行,每行输出一个人的编号,要求按编号从小到大输出。

数据范围

  • 2N202\le N\le 20
  • 2M10002\le M\le 1000
  • 所有 KiK_i 之和不超过 50005000
  • 输入保证描述了一种合法的悄悄话安排。

子任务

子任务 分值 限制
1 18 N=2N=2
2 16 M=3,N8M=3, N\le 8
3 19 M=3M=3
4 47 无额外限制