#115. 「一本通 3.5 例 2」最大半连通子图

「一本通 3.5 例 2」最大半连通子图

题目描述

原题来自:ZJOI 2007

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

G=(V,E)G'=(V',E') 满足,EE’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)(a, b)

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

输出格式

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

样例

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

数据范围与提示

对于 20%20\% 的数据,N18N \le 18
对于 60%60\% 的数据,N104N \le 10^4
对于 100%100\% 的数据,1N105,1M106,X1081\le N \le 10^5,1\le M \le 10^6,X\le 10^8