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

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

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:ZJOI 2007

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

G′=(V′,E′)G'=(V',E')G=(V,E) 满足,E’E’EEEE 中所有和 V’V’V 有关的边,则称 G’G’GGGG 的一个导出子图。若 G’G’GGGG 的导出子图,且 G’G’G 半连通,则称 G’G’GGGG 的半连通子图。若 G’G’GGGG 所有半连通子图中包含节点数最多的,则称 G’G’GGGG 的最大半连通子图。

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


Input

第一行包含三个整数 N,M,XN,M,XN,M,XN,MN,MN,M 分别表示图 GGG 的点数与边数,XXX 的意义如上文所述;
接下来 MMM 行,每行两个正整数 a,ba, ba,b,表示一条有向边 (a,b)(a, b)(a,b)

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


Output

应包含两行。第一行包含一个整数 KKK,第二行包含整数 C mod XC \bmod XCmodX


Sample Input

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

Sample Output

3
3

HINT

对于 20%20\%20% 的数据,N≤18N \le 18N18
对于 60%60\%60% 的数据,N≤104N \le 10^4N104
对于 100%100\%100% 的数据,1≤N≤105,1≤M≤106,X≤1081\le N \le 10^5,1\le M \le 10^6,X\le 10^81N105,1M106,X108


Source/Category


Submit Status