#R1002. HOLMES

HOLMES

题目描述

福尔摩斯是一位名侦探。他的助手华生经常给他提供大大小小的线索,在那之后福尔摩斯就会把这些线索存入他的记忆宫殿当中,供以后探案的时候用。华生提供的线索是基于某两个事件之间的相关联系的,如:ABA\to B,表示如果 AA 事件成立的话,BB 事件一定也成立(当且仅当 AA 成立但 BB 不成立的时候才产生矛盾),并且这些线索不会构成环状的关系,如: ABCAA\to B\to C\to\dots\to A

福尔摩斯接到了一桩案件,共由 DD 个事件组成,在这之前,华生已经向他提供了 MM 条有关这 DD 个事件的线索。先在已确定有 NN 个事件已经发生,福尔摩斯凭借这些线索和他的推理最多可以推出多少件一定发生的事件(包括已知发生的事件)?

格式

输入格式

第一行包括 33 个正整数,DD1D10001\leq D\leq 1000),表示事件的总数,MM1M1000001\leq M\leq100000),表示线索的数量,NN1ND1\leq N\leq D),表示已知发生的事件数。

接下来 MM 行,每行包括两个正整数 AABB1A,BD1\leq A,B\leq D),用来描述一条线索,表示如果 AA 事件发生的话,BB 事件一定发生。

输出格式

输出仅一行,表示福尔摩斯最多可以知道哪些事件发生了,从小到大输出。

样例数据

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

样例解释

样例1解释:2发生了,3一定会发生。导致2发生的只有1,所以1一定也发生了。

样例2解释:1或者2发生,都会导致3发生,现在3发生,无法确定到底是哪个导致的。

样例3解释:4发生了,是2或者3导致,2或者3一定是因为1导致的,所以1一定发生了,2和3也一定会发生。

Problem from: COCI 2009-2010 #6.