最大半连通子图

题目来源

ZJOI2007

题目描述

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

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

若$G'$是$G$所有半连通子图中包含节点数最多的，则称$G'$是$G$的最大半连通子图。给定一个有向图$G$，请求出$G$的最大半连通子图拥有的节点数$K$，以及不同的最大半连通子图的数目$C$。由于$C$可能比较大，仅要求输出$C$对$X$的余数。

输入格式

第一行包含三个整数$N, M, X$。$N, M$分别表示图$G$的点数与边数，$X$的意义如上文所述。

接下来$M$行，每行两个正整数$a, b(1\leq a, b\leq N)$，表示一条有向边$(a, b)$。

保证输入中没有重边，$N \leq 10^5, M \leq 10^6, X \leq 10^8$。

输出格式

一共两行，第一行包含一个整数$K$，第二行包含整数$C \bmod X$。

样例输入

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

样例输出

3
3