题目描述

原题来自：ZJOI 2007

一个有向图$\red{ G=(V,E) }$称为半连通的 (Semi-Connected) ，如果满足：$\red{\forall u,v\in V}$，满足$\red{ u→v}$ 或 $\red{v→u}$，即对于图中任意两点 $\red{u,v}$，存在一条 $\red{u}$ 到 $\red{v}$ 的有向路径或者从$\red{ v}$ 到 $\red{u}$ 的有向路径。

若 $\red{G’=(V’,E’)}$ 满足，$\red{E’}$ 是$\red{ E}$ 中所有和$\red{V’ }$有关的边，则称$\red{ G’ }$是$\red{ G}$ 的一个导出子图。若$\red{ G’ }$是$\red{ G }$的导出子图，且 $\red{G’ }$半连通，则称$\red{ G’}$ 为$\red{ G}$ 的半连通子图。若 $\red{G’ }$是 $\red{G }$所有半连通子图中包含节点数最多的，则称$\red{ G’ }$是$\red{ G }$的最大半连通子图。

给定一个有向图$\red{ G}$，请求出 $\red{G}$ 的最大半连通子图拥有的节点数 $\red{K}$，以及不同的最大半连通子图的数目 $\red{C}$。由于 $\red{C }$可能比较大，仅要求输出$\red{ C }$对 $\red{X}$ 的余数。

输入格式

第一行包含三个整数 $\red{N,M,X}$。$\red{N,M }$分别表示图$\red{G }$的点数与边数，$\red{X}$ 的意义如上文所述； 接下来$\red{ M}$ 行，每行两个正整数 $\red{a,b}$，表示一条有向边$\red{ (a,b)}$。

图中的每个点将编号为 $\red{1,2,3,⋯,N}$，保证输入中同一个$\red{ (a,b) }$不会出现两次。

输出格式

应包含两行。第一行包含一个整数$\red{ K}$，第二行包含整数 $\red{C \bmod X}$。

样例

输入样例

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

输出样例

3
3

提示

对于 $\red{20\%}$ 的数据，$\red{N \le 18}$； 对于$\red{ 60\%}$ 的数据，$\red{N \le 10^4}$； 对于$\red{ 100\% }$的数据，$\red{1\le N \le 10^5,1\le M \le 10^6,X\le 10^8}$。