CSG-CPC
Online Judge

1242 : 见面礼

         Time Limit: 1 Sec     Memory Limit: 512 Mb     Submitted: 679     Solved: 188    

Description

给定一个 \(n\) 个点 \(n\) 条边的无向图,你需要求有多少种选择图上的一个点 \(p\) 和一条边 \((x,y)\) 的方案,使得删去 \((x,y)\) 后图变成一棵树,且这棵树以 \(p\) 为根时每个节点的儿子个数均不超过 \(3\)保证至少存在一种这样的方案。

Input

输入的第一行一个整数 \(n\)\(2 \le n \le 10^5\)) 表示节点数,接下来 \(n\) 行每行两个整数 \(x,y\)\(1 \le x, y \le n\)) 描述图上的一条边。保证图中没有重边自环。

Output

输出一行一个正整数表示答案。

Sample

6
1 2
1 3
1 4
1 5
1 6
2 3
10

Hint

【样例解释 #0】

删除 \((1,2)\) 或者 \((1,3)\),并在 \(2,3,4,5,6\) 中选择一个节点作为根,可以得到所有的合法方案。因此输出为 \(2 \times 5 = 10\)

Author

THU