U384679 欢度元旦（hard）

（**本题与简单版只有数据范围的差别**） 元旦快要到了，到处张灯结彩、喜气洋洋。五（3）班的同学们也在准备着过一个很快乐的元旦。那么，主要的下手点就是联欢会了！

同学们计划做 $n$ 件有意义的事情，第 $i$ 件事情喜气值为 $i$。但是，这些事之间存在 $m$ 条依赖关系，比如制作完了灯笼才可以悬挂，擦完了黑板才能绘制板报…… 如果把事情编号按照执行顺序标位 $a_{1},a_{2}...a_{n}$。则对于整数 $i$（$1\le i \le n$），若 $max_{i-1}^{j=1}a_{j} \le a_{i}$，同学们就会高兴一次（$i=1$ 时 **一定** 满足条件）。 班长希望同学们很高兴，所以他问你最大的高兴次数。 老师希望同学们收收心，于是他问你最小的高兴次数。 **保证一定可以做完这 $n$ 件事情！**

第一行两个整数 $n,m$，表示事件数和依赖关系数。 接下来 $m$ 行，每行两个数 $u,v$，表示 $u$ 要在 $v$ 完成之前完成。

第一行一个整数，表示班长需要的答案。 第二行一个整数，表示老师需要的答案。

对于 $100$% 的数据，满足 $1 \le n,m \le 5\times10^5$。 本题 $20$ 个测试点，每个测试点 $5$ 分。 - 若你给班长的答案正确，则你可以获得 $2$ 分。 - 若你给老师的答案正确，则你可以获得 $3$ 分。