原题来自:ZJOI 2007
ZJOI 2007
一个有向图 G=(V,E) 称为半连通的(Semi-Connected),如果满足:∀u,v∈V,满足 u→v或 v→u,即对于图中任意两点 u,v,存在一条 u 到 v 的有向路径或者从 v 到 u 的有向路径。
G=(V,E)
(Semi-Connected)
∀u,v∈V
u→v
v→u
u,v
u
v
若 G'=(V',E')满足,E'是 E 中所有和V' 有关的边,则称G'是 G 的一个导出子图。若 G' 是 G 的导出子图,且 G' 半连通,则称 G' 为 G 的半连通子图。若G' 是 G 所有半连通子图中包含节点数最多的,则称 G' 是 G 的最大半连通子图。
G'=(V',E')
E'
E
V'
G'
G
给定一个有向图 G,请求出 G的最大半连通子图拥有的节点数K,以及不同的最大半连通子图的数目 C。由于 C 可能比较大,仅要求输出 C对 X 的余数。
K
C
X
第一行包含三个整数 N,M,X。N,M 分别表示图 G 的点数与边数,X 的意义如上文所述;
N,M,X
N,M
接下来 M 行,每行两个正整数 a,b,表示一条有向边 (a,b)。
M
a,b
(a,b)
图中的每个点将编号为 1,2,3,⋯,N,保证输入中同一个 (a,b)不会出现两次。
1,2,3,⋯,N
应包含两行。第一行包含一个整数 K,第二行包含整数C mod X。
C mod X
样例输入
6 6 200706031 22 11 32 45 66 4
样例输出
33
对于 20% 的数据, N≤18 ;
20%
对于 60% 的数据, N≤10^4 ;
60%
对于 100% 的数据, 1≤N≤10^5,1≤M≤10^6,X≤10^8 。
100%