[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$。