当前没有测试数据。

【例题3】最大半连通子图

题目描述

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

若$G'=(V',E')$满足$V' \subseteq V$，$E'$是$E$中所有跟$V'$有关的边，则称$G'$是$G$的一个导出子图。

若$G'$是$G$的导出子图，且$G'$半连通，则称$G'$为$G$的半连通子图。

若$G'$是$G$所有半连通子图中包含节点数最多的，则称$G'$是$G$的最大半连通子图。

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

输入格式

第一行包含三个整数$N$，$M$，$X$。

$N$，$M$分别表示图$G$的点数与边数，$X$的意义如上文所述。

接下来$M$行，每行两个正整数$a$，$b$，表示一条有向边$a \to b$。保证输入中同一个$a \to b$不会出现两次。

输出格式

共两行，第一行包含一个整数$K$。

第二行包含整数，表示$C \bmod X$。

数据范围与提示

对于$100\%$的数据，$1 \leq N \leq 10^5$，$1 \leq M \leq 10^6$，$1 \leq X \leq 10^8$。

样例

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

3
3