题目描述

Farmer John 有 N 个农场，编号为 1 ~ N。

有 M 条单向道路。每条道路连接两个不同的农场（无自环）。一个农场到另一个农场之间最多有一条单向道路（无重边）。

现在 John 要将若干个农场设置为比赛场地，这些比赛场地间的道路设置为比赛跑道。设置完后，要求对于任意两个比赛场地，假设为农场 x 和农场 y，至少存在一条从 x 到 y 的路径，或者至少存在一条从 y 到 x 的路径，并且路径上不能经过非比赛场地和非比赛跑道。

问：

（1）John 最多可以把多少个农场设置为比赛场地？

（2）在满足第（1）问的前提下，他最多有多少种不同的设置方案？答案可能很大，你需要输出答案 mod P。

输入格式

第一行：三个整数 $N, M, P$;

接下来 $M$ 行：每行两个整数 $x, y$，表示从农场 x 到农场 y 有一条单向道路。数据保证没有自环，没有重边。

输出格式

共两行，每行一个整数：

第一行的整数表示第（1）个问题的答案；

第二行的整数表示第（2）个问题的答案 mod P。

样例输入

5 5 321
1 2
2 1
1 4
2 3
5 3

样例输出

3
2

样例解释

原地图：

最多可以设置 3 个农场为比赛场地。

有两种设置方案（黄色点和边代表比赛场地和跑道）：

（1）

（2）

提示

100% 的数据：$N ≤ 10^5$，$M ≤ 10^6$，$P ≤ 10^8$。