Description

JYY has recently become obsessed with strong connectivity in graphs. For any directed graph, JYY wants to add some edges to make the graph strongly connected. Now JYY is given a directed graph with $n$ vertices and $m$ edges, where the vertices are numbered from $1$ to $n$.

JYY wants to know:

• In the given graph, what is the maximum number of vertices that can be chosen such that every pair of these vertices is mutually reachable in the original graph?

• In the given graph, what is the minimum number of edges that need to be added to make the graph strongly connected?

A directed graph $G(V,E)$ is strongly connected if and only if for any two distinct vertices $a,b\in V, a\neq b$, there exist paths $a\to b$ and $b\to a$.

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $x$ and $y$, indicating that there is a directed edge from $x$ to $y$ in the graph.

Output Format

Output two lines. The first line is the answer to the first question, and the second line is the answer to the second question.

4 3
1 4
2 3
2 4

1
2

Hint

Sample Explanation 1

For the first question, it is impossible to choose two vertices that are mutually reachable, so the answer is $1$.

For the second question, one optimal way with the minimum number of added edges is $(3,1)$ and $(4,2)$, so the answer is $2$.

Constraints

For $100\%$ of the testdata, $1\leq n\leq 10^5,1\leq m\leq 3\times 10^5$.

Translated by ChatGPT 5