跳蚤国运动会在首都跳蚤利亚举行,来自全国各地的跳蚤居民蜂拥而至。为了确保运动会期间的交通秩序,跳蚤国王决定对首都的道路进行管制。
跳蚤利亚的道路系统可以看作一张由
国王需要选择一部分道路保持开放,其余道路暂时封闭。
然而,为了保证观众能顺利抵达赛场并为心仪的战队加油,开放的道路必须满足一系列特殊限制:
对于第
- 边简单路径的定义是:不经过重复道路的路径,且一条道路不允许从两个方向经过。
- 不同的边简单路径的定义是:经过的路口序列不完全相同的边简单路径。
- 特别地,路径可以只经过一个路口,在
时这类路径也应被计入。
你需要帮助跳蚤国王计算出满足所有限制条件的道路开放方案数,答案对
形式化题面:
给定一张
满足给出的 条限制:第 条限制是在 上,从 到 必须至少有 条不同的边简单路径( )。
答案对
输入格式
第一行三个整数
接下来
接下来
输出格式
一行一个整数,表示满足所有限制条件的道路开放方案数对
样例零
input
4 6 4 1 2 1 3 1 4 2 3 2 4 3 4 1 2 1 1 1 2 2 3 2 2 4 2
output
19
样例一~七
见下发文件。
数据范围
对于所有数据,保证
子任务编号 | 分值 | 特殊性质 | |
---|---|---|---|
无 | |||
无 | |||
无 | |||
无 | |||
无 | |||
无 |
时间限制:
空间限制: