#5033. [Jsoi2014]强连通图

内存限制:256 MiB 时间限制:10 Sec

题目描述

JYY最近痴迷于图的强连通性,所以对于任何有向图,JYY都希望增加一 些边使得这个图变成强连通图。JYY现在得
到了一个N个点M条边的有向图。所有点从1到N编号。
JYY想知道:
1、 在给定的图中,最多能选出多少个点,使得这些点在原图中两两可达?
2、 在给定的图中,最少增加多少条边,可以使得这个图变成强连通图?
其中,一个有向图G(V,E)是强连通的,当且仅当任意顶点a,b ∈ E (a≠b)之间都存在a -> b和b -> a的路径。
由于加边操作是很麻烦的,JYY保证,在最优方案中,只需要至多增加1000条边就可以把原图变成强连通图。

输入格式

第一行包含两个整数N和M。
接下来M行,每行两个整数x和y,表示图中有一条从点x到点y的有向边。

输出格式

输出文件的第一行包含一个整数C,表示JYY第一个问题的答案;
输出文件的第二行包含一个整数K,表示JYY第二个问题的答案;

样例

样例输入


			
1 3
1 4
2 3
2 4

样例输出


			
1
2

数据范围与提示