题目描述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

提示Hint

【样例解释 #0】

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

出题Author

THU

来源Source

第九届中国大学生程序设计竞赛（深圳）-（CCPC2023-Shenzhen）