3369. 三千米健身步道

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

输入格式

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

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

输出格式

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

样例

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

67 人解决,77 人已尝试。

83 份提交通过,共有 183 份提交。

3.1 EMB 奖励。

创建: 2 年,4 月前.

修改: 2 年,4 月前.

最后提交: 1 周,4 天前.

来源: 2017.9.27 ACM 选拔赛

题目标签