1850. 预言家困境

时间限制 2000 ms   内存限制 128 MB

狼人杀是一款桌面游戏,主题是好人和狼人两个阵营的对抗。

现在有 $n$ 个人聚在一起玩狼人杀。所有人指认一个人是狼人,好人说的一定说真话,狼人一定说谎。

在好人阵营中,有一位预言家,可以分辨一部分人是好人还是狼人。Alice 抽到了预言家,除了知道她自己是预言家外,又额外知道了 $p+q$ 个人的身份。现在 Alice 希望通过已有信息,尽可能多的确认每个人的身份。

输入数据

第一行有一个整数 $n$,代表玩家总数($ 2\leq n\leq 5 \times 10^5 $)。

第二行有 $n-1$ 个整数 $c_i$,代表除 Alice 外,其他人指认的人的编号。编号从 1 开始,Alice的编号为 $n$($ 1 \leq c_i \leq n $)。

第三行的第一个整数 $p$ ,代表Alice知道了 $p$ 个人的身份是好人,其余 $p$ 个整数分别代表他们的编号($p \geq 0$)。

第四行的第一个整数 $q$,代表Alice知道了 $q$ 个人的身份是狼人,其余 $q$ 个整数分别代表他们的编号($q \geq 0, p+q < n$)。

数据保证没有冲突。

输出数据

输出包含两行。

第一行的第一个整数 $p'$,代表Alice可以确认的其他好人数量为 $p'$,其余 $p'$ 个整数分别代表他们的编号,按编号从小到大输出。

第二行的第一个整数 $q'$,代表Alice可以确认的狼人数量为 $q'$,其余 $q'$个整数分别代表他们的编号,按编号从小到大输出。

样例输入

复制
4
2 3 2
1 1
1 2 \n
 · · \n
 · \n
 · \n

样例输出

复制
2 1 3
1 2 · · \n
 · \n

样例说明

1和3都指认2是狼人,2指认3是狼人。Alice知道1是好人,2是狼人,因此可以得出,狼人2指认的3是好人。

提交

请先 登录

© 2024 FAQs Contact About