#P6804. [2020福建冬令营]赢家
[2020福建冬令营]赢家
题目描述
给定一张有 个点、 条边的简单无向图。把每条边任选一个方向,得到一张有向图。若存在一个点 ,使得从点 和点 出发都能到达 ,则称这种定向合法。允许长度为零的路径。
求所有 种定向中合法的方案数,对 取模。
输入格式
第一行三个正整数 ,其中 为子任务编号。接下来 行,每行两个整数 ,描述一条无向边。
输出格式
输出一个整数,表示合法方案数取模后的结果。
样例
3 2 1
1 3
2 3
3
三种合法定向分别为 ,,。
4 5 1
1 3
2 3
1 4
2 4
3 4
30
5 6 1
1 3
2 3
3 4
3 5
1 4
2 5
55
数据范围
对于全部数据,,,。
原题分为四个子任务。第 1 组 30 分,。第 2 组 15 分,点 和点 之间恰有一条简单路径。第 3 组 20 分,。第 4 组 35 分,无额外限制。