Token Transfer in a Directed Acyclic Graph Board Game

This problem is based on a board game whose map can be abstracted as a directed acyclic graph (DAG) with \( n \) nodes and \( m \) edges (the graph is not necessarily connected). Player Little C traverses this map. He can move to a node if and only if every node that has a directed path to that node has already been visited. Note that the set of nodes that are available to walk to does not necessarily depend on his current position; any node that satisfies the condition is allowed.

Every time Little C steps into a node whose label is strictly greater than all previously visited nodes, an event occurs. In this event, with probability \( \frac{1}{2} \) he gains 1 chip from his opponent, and with probability \( \frac{1}{2} \) he loses 1 chip to his opponent. Both players start with \( 1919810 \) chips.

Your task is to help Little C compute the following two quantities assuming he can choose an optimal walking order that is a valid topological ordering (i.e. a linear extension of the partial order defined by the DAG):

• Best-case scenario: The maximum number of chips he can gain (i.e. assume that every time the event occurs, he gains a chip) if he chooses an order that maximizes the number of record events.
• Worst-case scenario: The maximum number of chips he will lose (i.e. assume that every time the event occurs, he loses a chip) if he chooses an order that minimizes the number of record events.
</p>

A record event is defined as follows. Let \( A[1 \ldots n] \) be the order in which the vertices (labeled from \( 1 \) to \( n \)) are visited. For each \( i \) (\( 1 \le i \le n \)), if \( A[i] > \max\{A[1], A[2], \ldots, A[i-1]\} \) (with the convention that the condition holds vacuously for \( i=1 \)), then a record event occurs.

Given the DAG, determine the maximum possible number of record events over all valid topological orderings (for the best-case scenario) and the minimum possible number of record events (for the worst-case scenario). Output these two numbers on one line separated by a space.

inputFormat

The first line of input contains two integers \( n \) and \( m \) (the number of nodes and edges respectively). Each of the following \( m \) lines contains two integers \( u \) and \( v \) indicating a directed edge from \( u \) to \( v \). It is guaranteed that the graph is a directed acyclic graph (DAG).

outputFormat

Output two integers separated by a space: the first is the maximum number of chips Little C can gain in the best-case scenario, and the second is the number of chips he loses in the worst-case scenario.

sample

3 0

3 1

</p>