AT_abc378_f [ABC378F] Add One Edge 2

给定一棵有 $N$ 个顶点的树。第 $i$ 条边 $(1\leq i\leq N-1)$ 连接了顶点 $u_i$ 和顶点 $v_i$，且为无向边。 在给定的树上添加一条无向边后，得到的图一定恰好包含一个简单环。 请计算满足以下所有条件的图的个数： - 图是简单图。 - 图中环上所有顶点的度数都为 $3$。

输入以以下格式从标准输入读入。 > $N$ $u_1$ $v_1$ $u_2$ $v_2$ $\cdots$ $u_{N-1}$ $v_{N-1}$

请输出答案。

## 限制条件 - $3\leq N\leq 2\times 10^5$ - $1\leq u_i,v_i\leq N$ - 给定的图是一棵树 - 输入的所有数值均为整数 ## 样例解释 1 添加一条连接顶点 $2$ 和顶点 $4$ 的边后，得到的图是简单图，且环上所有顶点的度数都为 $3$，因此满足条件。 ## 样例解释 2 有时不存在满足条件的图。 由 ChatGPT 4.1 翻译