[JSOI2014] 强连通图
题目描述
JYY 最近痴迷于图的强连通性,所以对于任何有向图,JYY 都希望增加一些边使得这个图变成强连通图。JYY现在得到了一个 $n$ 个点 $m$ 条边的有向图,所有点从 $1$ 到 $n$ 编号。
JYY 想知道:
- 在给定的图中,最多能选出多少个点,使得这些点在原图中两两可达?
- 在给定的图中,最少增加多少条边,可以使得这个图变成强连通图?
其中,一个有向图 $G(V,E)$是强连通的,当且仅当任意顶点 $a,b\in V,a\neq b$之间都存在 $a\to b$ 和 $b\to a$ 的路径。
输入输出格式
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行,每行两个整数 $x$ 和 $y$,表示图中有一条从 $x$ 到 $y$ 的有向边。
输出格式
两行,第一行表示第一个问题的答案,第二行表示第二个问题的答案。
输入输出样例
输入样例 #1
4 3
1 4
2 3
2 4
输出样例 #1
1
2
说明
### 样例解释 1
对于第一个问题,无法选出互相连通两个点,答案为 $1$。
对于第二个问题,一种加边数最小的方案为 $(3,1)$ 和 $(4,2)$,答案为 $2$。
### 数据范围
对于 $100\%$ 的数据,$1\leq n\leq 10^5,1\leq m\leq 3\times 10^5$。