#2969. 「COCI 2010.03.20」HOLMES

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

题目描述

译自 COCI 2010.03.20 T5. HOLMES

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

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

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

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

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

输入格式

第一行: D,M,N
接下来 M 行:每行两个整数,表示一组推论 A_i, B_i
接下来 N 行:第 i 行有一个整数 S_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 一定会发生。

数据范围与提示

1\le D\le 1000, 1\le M\le 10^5, 1\le N, X_i, A_i, B_i\le D .