1242 : 见面礼

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\)。

Source

Author

THU