School Network Connectivity

You are given n schools (with \(1\le n\le 10000\)) and m one-way network connections. Each connection is represented as a directed edge from school u to school v.

The task is twofold:

1. Determine the minimum number of schools that must be chosen to host the shared software (referred to as the mother machines) so that every school can access the software. In other words, from at least one of the selected schools there should be a path to every other school.
2. Determine the minimum number of additional one-way connections needed so that if any school is chosen as the mother machine, every other school can access the software (i.e. the network becomes strongly connected).

A standard way to solve this problem is to contract the graph into its strongly connected components (SCCs). Let the resulting condensation graph have \(k\) nodes. Then:

• The answer to the first part is the number of SCCs with no incoming edges.
• If \(k=1\) (i.e. the whole graph is strongly connected), no additional edge is needed. Otherwise, the answer to the second part is \(\max(\text{number of SCCs with no incoming edges},\; \text{number of SCCs with no outgoing edges})\).

Note: In the case of a single school (n = 1), it is considered strongly connected by itself.

inputFormat

The first line contains two integers n and m, representing the number of schools and the number of one-way connections, respectively.

The following m lines each contain two integers u and v (1-indexed) indicating a directed connection from school u to school v.

outputFormat

Output two integers separated by a space on a single line:

• The minimum number of schools that need to be chosen as mother machines so that every school is covered.
• The minimum number of additional one-way connections required to make the network strongly connected (so that any school can serve as the mother machine for all others).

sample

5 4
1 2
2 3
3 1
4 5

2 2