#2969. 「COCI 2010.03.20」HOLMES

内存限制:32 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 COCI 2010.03.20 T5「HOLMES

DD 个事件,编号分别为 1N1\ldots N

福尔摩斯有 MM 组形如 ABA\rightarrow B 的推论,表示「如果事件 AA 发生,那么事件 BB 一定会发生」。请注意,这不代表「如果 AA 不发生,BB 就一定不会发生」。

福尔摩斯的这 MM 组推论可以形成链式结构,例如 ABCA\rightarrow B\rightarrow C,但一定不会形成环,如 ABCAA\rightarrow B\rightarrow C\rightarrow \dots \rightarrow A

已知事件 S1SNS_1\ldots S_N 会发生,试求哪些事件一定会发生。

Update: 原题题意不清(或者是我语文太差),补充一句,这样才能解释样例 1。对于一个事件 XX,如果存在推论 Y1X,Y_1\rightarrow X, Y2XY_2\rightarrow X,那么「事件 XX 一定会发生」当且仅当『「事件 Y1Y_1 一定会发生」或「事件 Y2Y_2 一定会发生」……』

输入格式

第一行:D,M,ND,M,N
接下来 MM 行:每行两个整数,表示一组推论 Ai,BiA_i, B_i
接下来 NN 行:第 ii 行有一个整数 SiS_i

输出格式

一行,若干个整数,表示一定会发生的事件。

以任意顺序输出均可 请按照编号递增的顺序输出,传题人懒得写 SPJ

样例

样例输入 1

3 2 1
1 2
2 3
2

样例输出 1

1 2 3

样例输入 2

3 2 1
1 3
2 3
3

样例输出 2

3

样例说明 2

只知事件 3 发生,无法推出是事件 1 导致事件 3 发生还是事件 2 导致事件 3 发生。

样例输入 3

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

样例输出 3

1 2 3 4

样例说明 3

事件 4 发生,则事件 2 和事件 3 至少有一者发生;
无论是何者发生,其条件都是事件 1 一定发生;
因为事件 1 一定发生,因此事件 2, 3 都一定发生。

样例输入 4

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

样例输出 4

3 4

样例说明 4

事件 3 发生,则事件 1 和 2 一定有一者发生;
若事件 1 和 2 中有任意一者发生,则事件 4 一定会发生。

数据范围与提示

1D1000,1\le D\le 1000, 1M105,1\le M\le 10^5, 1N,1\le N, Xi,X_i, Ai,A_i, BiDB_i\le D.