9558 - 强连通图

JYY 最近痴迷于图的强连通性,所以对于任何有向图,JYY 都希望增加一些边使得这个图变成强连通图。JYY现在得到了一个 n 个点 m 条边的有向图,所有点从 1n 编号。

JYY 想知道:

  • 在给定的图中,最多能选出多少个点,使得这些点在原图中两两可达?

  • 在给定的图中,最少增加多少条边,可以使得这个图变成强连通图?

其中,一个有向图 G(V,E)是强连通的,当且仅当任意顶点 a,b\in V,a\neq b之间都存在 a\to bb\to a 的路径。

输入

第一行包含两个整数 nm

接下来 m 行,每行两个整数 xy,表示图中有一条从 xy 的有向边。

输出

两行,第一行表示第一个问题的答案,第二行表示第二个问题的答案。

样例

输入

4 3
1 4
2 3
2 4

输出

1
2

提示

样例解释 1

对于第一个问题,无法选出互相连通两个点,答案为 1

对于第二个问题,一种加边数最小的方案为 (3,1)(4,2),答案为 2

数据范围

对于 100\% 的数据,1\leq n\leq 10^5,1\leq m\leq 3\times 10^5

来源

江苏省选

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题