Background

Little C is a high school student who loves board games. Now he is stuck on a board game. Please help him.

Problem Description

The map of this board game can be seen as a directed acyclic graph with $n$ vertices and $m$ edges (not necessarily connected). Little C walks on this map. Little C can walk to a vertex if and only if all vertices that can reach this vertex have already been visited by Little C. Little C will visit every vertex exactly $1$ time, and which vertices he can visit does not depend on his current position (that is, he may visit a vertex that has no edge connected to his current vertex, as long as the condition above is satisfied).

Each time Little C visits a vertex whose label is larger than all previously visited vertices, he has probability $\frac{1}{2}$ to get $1$ chip from the opponent, and probability $\frac{1}{2}$ to give the opponent $1$ chip. Initially, both sides have $1919810$ chips.

Little C’s luck changes a lot, so he wants you to compute:

• In the best case, i.e. every time he can get a chip from the opponent, the number of chips he can obtain with an optimal walking strategy.
• In the worst case, i.e. every time the opponent can get a chip from him, the number of chips he will lose with an optimal walking strategy.

Input Format

The first line contains two positive integers $n, m$.

The next $m$ lines each contain two positive integers $u, v$, meaning there is a directed edge $(u, v)$ on the map. Multiple edges may exist.

Output Format

Output two lines, each containing one positive integer. The first line is the number of chips Little C can get in the best case. The second line is the number of chips Little C will lose in the worst case.

3 2
1 2
1 3

3
2

Hint

Sample Explanation

In the best case, the walking order is $1-2-3$. In the worst case, the walking order is $1-3-2$.

Scoring

For each test case:

• If your output format is wrong, or both lines are incorrect, you will get $0$ points.
• If your first line is correct and the second line is wrong, or the second line is correct and the first line is wrong, you will get $40 \%$ of the points for this test case.
• Otherwise, you will get $100 \%$ of the points for this test case.

Constraints

For $20\%$ of the testdata, $1 \le n, m \le 10$.

For $40\%$ of the testdata, $1 \le n, m \le 2000$.

For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $1 \le u, v \le n$.

Translated by ChatGPT 5