3369. 三千米健身步道

单点时限: 2.0 sec

内存限制: 256 MB

华师大是一个巨大的学校,众所周知,华师大的地图是一棵树,有 座教学楼,这些教学楼之间由 条道路相连,每条道路的长度都是一千米。

现在华师大投资建设一个「三千米健身步道」。为了让同学们不带喘气的跑(走)完这个健身步道,这个健身步道必须有一个起点,一个终点,中间是一段连续的三千米的跑道。华师大决定利用现有的 条道路建设这一个健身步道。问总共有多少种方案?

注意,起点和终点交换算同一种方案。

输入格式

第一行为 ,表示教学楼数量,教学楼编号从

接下来 行,每行为 ,表示 之间有道路相连。

输出格式

输出方案数。如果不存在,输出

样例

Input
6
1 2
2 3
3 4
4 5
4 6
Output
3

65 人解决,75 人已尝试。

81 份提交通过,共有 181 份提交。

3.2 EMB 奖励。

创建: 2 年,1 月前.

修改: 2 年,1 月前.

最后提交: 2 月前.

来源: 2017.9.27 ACM 选拔赛

题目标签