Strong Connectivity Augmentation

JYY is fascinated by strong connectivity in directed graphs. Given a directed graph with ( n ) vertices and ( m ) edges (vertices are numbered from 1 to ( n )), JYY wants to answer the following two questions:

1. What is the maximum number of vertices that can be selected such that every pair among these vertices is mutually reachable in the original graph?

2. What is the minimum number of edges that need to be added so that the entire graph becomes strongly connected?

A directed graph ( G(V, E) ) is strongly connected if and only if for every two distinct vertices ( a, b \in V ), there exists a path from ( a ) to ( b ) and a path from ( b ) to ( a ).

Note: For the first question, note that a set of vertices is pairwise mutually reachable if and only if they all belong to the same strongly connected component (SCC) of the graph. Thus, the answer is the size of the largest SCC. For the second question, after condensing the graph into its SCCs (which forms a Directed Acyclic Graph), the minimum number of added edges equals ( \max(\text{number of SCCs with zero in-degree},, \text{number of SCCs with zero out-degree}) ) (with the exception that if the graph has only one SCC then no edge is needed).

inputFormat

The first line of input contains two integers ( n ) and ( m ), representing the number of vertices and edges respectively. Each of the following ( m ) lines contains two integers ( u ) and ( v ), indicating a directed edge from vertex ( u ) to vertex ( v ).

outputFormat

Output two integers on separate lines. The first integer is the maximum number of vertices that can be chosen such that every pair of these vertices is mutually reachable (i.e., the size of the largest strongly connected component). The second integer is the minimum number of edges that need to be added to make the entire graph strongly connected.

sample

3 3
1 2
2 3
3 1

3
0