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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:ZJOI 2007

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

G'=(V',E') 满足, 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 ,表示一条有向边 (a, b)

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

输出格式

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

样例

样例输入

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

样例输出

3
3

数据范围与提示

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