#L4243. 「NordicOI 2021」Amazing Whispers

    ID: 4818 传统题 1000ms 256MiB 尝试: 3 已通过: 0 难度: 8 上传者: 标签>2021NordicOI图论二分图匹配组合优化传递路径约束满足

「NordicOI 2021」Amazing Whispers

题目描述
译自 NordicOI 2021 Day2 T3「Amazing Whispers」

一群朋友想玩一个神奇的传话游戏,这个游戏的规则如下:

你有 N×MN \times M 个人,分成 MM 组,每组有 NN 个人。
一个秘密短语被分成 NN 个不同的信息,每个11 的成员会收到一个不同的信息。
这些信息会从组 11 传递到组 22,再从组 22 传递到组 33,以此类推,直到最终从组 M1M-1 传递到组 MM。每条信息都会被传递,但每个人只能听到一条信息。

为了让观察者更难追踪信息,每个组 ii 的人会假装对组 i+1i+1 的最多 NN 个人传话。实际上,只有其中一个人会真正听到信息,其他人只是被假装传话。这样,观察者就无法知道组 i+1i+1 中的哪个人真正收到了信息。组 ii 的人已经安排好,让组 i+1i+1 的每个人都能听到一条信息。

当所有信息到达组 MM 后,它们会被大声读出来。结果发现,所有信息都成功传递,除了其中一条被替换成了粗鲁的话。AA 号人最初持有丢失的信息,而 BB 号人是唯一一个读出粗鲁话的人。你不知道在传递过程中哪个阶段发生了替换。谁可能是这个恶作剧的罪魁祸首?
你不知道信息是如何传递的。你只知道那些假装传话的人的配对情况。


输入格式
第一行包含四个整数 NN, MM, AA, BB,如题目所述。
人们的编号从 00(N×M)1(N \times M) - 1,编号为 pp 的人属于组 p/N+1\left \lfloor{p/N}\right \rfloor + 1。(x\left \lfloor{x}\right \rfloor 表示不大于 xx 的最大整数。)

接下来是 N×(M1)N \times (M - 1) 行。第 ii 行描述第 ii 个人假装对谁传话。

每行以一个整数 KiK_i 开头,表示第 ii 个人假装对 KiK_i 个人传话。接下来是 KiK_i 个整数 Ri,0Ri,Ki1R_{i,0} \ldots R_{i,K_i-1},指定那些人是谁。这些人总是属于第 ii 个人所在组的下一组,这些数字满足 $\left \lfloor{R_{i,j}/N}\right \rfloor = \left \lfloor{i/N}\right \rfloor + 1$。


输出格式
输出的第一行应包含一个整数 SS,表示可能是恶作剧罪魁祸首的人数。
接下来的 SS 行应列出这些人,每行一个人,按编号升序排列。


样例 1
输入

2 3 1 5
1 3
1 2
2 5 4
2 4 5

输出

3
1
2
5

样例 2
输入

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

输出

3
0
4
6

数据范围与提示
对于所有输入数据,满足:

  • 2N202 \le N \le 20
  • 2M10002 \le M \le 1000
  • 所有 KiK_i 的总和不超过 50005000
  • 输入描述了一种有效的传递方式

详细子任务附加限制及分值如下表所示。

子任务 分值 附加限制
1 18 N=2N = 2
2 16 M=3M = 3, N8N \le 8
3 19 M=3M = 3
4 47 无附加限制