P5603 Little C and Board Games

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

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.

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 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.

**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