小 C 与桌游

题目背景

小 C 是一个热爱桌游的高中生,现在他被一个桌游难住了,快来帮帮他!

题目描述

这个桌游的地图可以被抽象成一个 $n$ 个点,$m$ 条边的**有向无环图**(**不保证连通**),小 C 在这个地图上行走,小 C 能走到某个点当且仅当能够到达这个点的所有点都已经被小 C 走到。小 C 会走到每个点恰好 $1$ 次,并且他能走到哪些点与他当前所在的点没有关系(即可以走到与当前所在的点没有连边的点,只要满足之前的条件)。 小 C 每走到一个标号比之前走到的点都大的点,他就会有 $\frac{1}{2}$ 的概率从对手那里拿到 $1$ 块筹码,有 $\frac{1}{2}$ 的概率给对手 $1$ 块筹码,双方初始各有 $1919810$ 个筹码。 小 C 的运气时好时坏,所以他希望你帮他计算出: - 在最优情况下,即他每次都能从对手那里拿到筹码时,他采取最优的行走方式能得到的筹码数。 - 在最劣情况下,即对手每次都能从他那里拿到筹码时,他采取最优的行走方式会失去的筹码数。

输入输出格式

输入格式


第一行两个正整数 $n, m$。 接下来 $m$ 行,每行两个正整数 $u, v$,表示地图上有一条有向边 $(u, v)$,不保证无重边。

输出格式


输出两行,每行一个正整数,第一行表示最优情况下小 C 能拿到的筹码数,第二行表示最劣情况下小 C 会失去的筹码数。

输入输出样例

输入样例 #1

3 2
1 2
1 3

输出样例 #1

3
2

说明

**样例解释** 最优情况下的行走方式是 $1-2-3$,最劣情况下的行走方式是 $1-3-2$。 **计分方式** 对于每一个测试点: - 如果你输出格式错误或者两行都不正确,将会得到 $0$ 分。 - 如果你的输出第一行正确,第二行错误或第二行正确,第一行错误,将会得到这个测试点 $40 \%$ 的分数。 - 否则,你将会得到这个测试点 $100 \%$ 的分数。 **数据范围** 对于 $20\%$ 的数据,$1 \le n, m \le 10$。 对于 $40\%$ 的数据,$1 \le n, m \le 2000$。 对于 $100\%$ 的数据,$1 \le n, m \le 5 \times 10^5$,$1 \le u, v \le n$。