#8732. 「一本通 3.5 例 2」最大半连通子图
「一本通 3.5 例 2」最大半连通子图
题目描述
原题来自:ZJOI 2007
一个有向图 称为半连通的 (Semi-Connected),如果满足:,满足 或 ,即对于图中任意两点 ,存在一条 到 的有向路径或者从 到 的有向路径。
若 满足, 是 中所有和 有关的边,则称 是 的一个导出子图。若 是 的导出子图,且 半连通,则称 为 的半连通子图。若 是 所有半连通子图中包含节点数最多的,则称 是 的最大半连通子图。
给定一个有向图 ,请求出 的最大半连通子图拥有的节点数 ,以及不同的最大半连通子图的数目 。由于 可能比较大,仅要求输出 对 的余数。
输入格式
第一行包含三个整数 。 分别表示图 的点数与边数, 的意义如上文所述;
接下来 行,每行两个正整数 ,表示一条有向边 。
图中的每个点将编号为 ,保证输入中同一个 不会出现两次。
输出格式
应包含两行。第一行包含一个整数 ,第二行包含整数 。
样例
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
3
3
数据范围与提示
对于 的数据,;
对于 的数据,;
对于 的数据,。