#P2272. [ZJOI2007] 最大半连通子图

[ZJOI2007] 最大半连通子图

题目描述

一个有向图 G=(V,E)G=\left(V,E\right) 称为半连通的 (Semi-Connected),如果满足:u,vV\forall u,v\in V,满足 uvu\to vvuv\to u,即对于图中任意两点 u,vu,v,存在一条 uuvv 的有向路径或者从 vvuu 的有向路径。

G=(V,E)G'=\left(V',E'\right) 满足 VVV'\subseteq VEE'EE 中所有跟 VV' 有关的边,则称 GG'GG 的一个导出子图。若 GG'GG 的导出子图,且 GG' 半连通,则称 GG'GG 的半连通子图。若 GG'GG 所有半连通子图中包含节点数最多的,则称 GG'GG 的最大半连通子图。

给定一个有向图 GG,请求出 GG 的最大半连通子图拥有的节点数 KK,以及不同的最大半连通子图的数目 CC。由于 CC 可能比较大,仅要求输出 CCXX 的余数。

输入格式

第一行包含两个整数 N,M,XN,M,XN,MN,M分别表示图 GG 的点数与边数,XX 的意义如上文所述。

接下来 MM 行,每行两个正整数 a,ba,b,表示一条有向边 (a,b)\left(a,b\right)。图中的每个点将编号为 1,2,3N1,2,3\dots N,保证输入中同一个(a,b)\left(a,b\right)不会出现两次。

输出格式

应包含两行,第一行包含一个整数 KK,第二行包含整数 CmodXC\bmod X

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

提示

对于 100%100\% 的数据,N105N\le 10^5M106M\le 10^6X108X\le 10^8