eelpi是一个异世界的剑士!
现在,eelpi被困在了一个迷宫里,这个迷宫可以看作一个有 $n$ 个结点(用 $[1,n]$ 的序号表示),$m$ 条边的弱连通(所有的有向边替换为无向边后的图为连通图)的有向无环图,并且图中有一个出口在结点 $S$,eelpi需要找到这个出口 $S$!
eelpi还会法术,他通过法术知道了对于每个结点 $u$,都有一个值 $g_u$,表示通过起点为 $u$ 的边 $u\to v$ 后仍然能到达 $S$ 的 $v$ 的数量(即 $v$ 就是 $S$ 或者 $v$ 能到 $S$,很明显 $g_S=0$)。
现在eelpi想知道有哪些结点可能是出口,也就是 $S$ 点,但是他需要集中精力面对迷宫里的怪兽,所以请你帮助他解决这个问题吧!
由于本题数据量很大,所以请勿使用过慢的输入输出方式。特别的,C++选手请勿使用没有关闭流同步的cin
和cout
、Java选手请勿使用Scanner
。
第一行两个整数$n,m (2\le n\le 10^5,1\le m\le 10^6)$,分别表示点和边的数量。
接下来一行 $n$ 个整数,其中第 $i$ 个整数表示 $g_i\ (0\le g_i\le n)$。
接下来一共 $m$ 行,每行两个整数 $u,v(1\le u\le n,1\le v\le n,u\not=v)$,表示有一条从 $u$ 到 $v$ 的有向边。
输入数据保证给出的图是弱连通的有向无环图,并且没有重边,也就是不会有某两行的$u,v$分别相等。
输入保证至少能找到一个点是 $S$ 点。
第一行为一个整数 $cnt$,表示有多少个点可能是 $S$。
第二行为 $cnt$ 个整数,按编号从小到大的顺序输出可能是 $S$ 的点。
5 5 1 1 0 0 0 1 2 2 3 1 3 1 4 2 5
· \n · · · · \n · \n · \n · \n · \n · \n
1 5
\n \n
当 $S=5$ 时
可以证明,如果令其他点是 $S$,则无法满足给出的 $g$ 的数值。