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