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