2017.9.27 ACM 选拔赛

H. 三千米健身步道

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

输入格式

第一行为 $n$ $(2 \leq n \leq 1000)$,表示教学楼数量,教学楼编号从 $1$ 到 $n$。

接下来 $n - 1$ 行,每行为 $u_i,v_i$ $(1 \leq u_i, v_i \leq n, u_i \neq v_i)$,表示 $u_i, v_i$ 之间有道路相连。

输出格式

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

样例

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