题目背景

小 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 会失去的筹码数。

3 2
1 2
1 3

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$。