#10000213. 【ABC378】F - Add One Edge 2

問題文 | 题目描述

頂点の木が与えられます。 番目の辺 は頂点 と頂点 を双方向に結んでいます。
给定 个顶点的树。第 条边 是连接顶点 与顶点 的双向边。

与えられた木に無向辺を一本追加して得られるグラフは、必ずちょうど一つの閉路を含みます。
向给定的树中添加一条无向边，得到的图将恰好包含一个环。

そのようなグラフのうち、以下の条件を全て満たすものの個数を求めてください。
求满足以下所有条件的图的数量：

• グラフは単純グラフ
  图是简单图
• グラフの閉路に含まれる頂点の次数は全て 3
  图的环中包含的顶点的度数均为

入力 | 输入

入力は以下の形式で標準入力から与えられる。
输入从标准输入按照如下规则给出：

出力 | 输出

答えを出力せよ。
输出答案即可

入力例 1 | 输入样例 1

61 22 33 44 53 6

出力例 1 | 输出样例 1

1

頂点  と頂点  を結ぶ辺を追加して得られるグラフは単純グラフであり、閉路に含まれる頂点の次数は全て  なので条件を満たします。
添加连接顶点 与顶点 的边所得到的图是一个简单图，并且环中包含的顶点的度数均为 ，因此满足条件。

入力例 2 | 输入样例 2

71 22 73 57 36 24 7

出力例 2 | 输出样例 2

0

条件を満たすグラフが存在しない場合もあります。
此时不存在满足条件的图

制約 | 约定

• 与えられるグラフは木である
  给定的图是一棵树
• 入力される数値は全て整数
  输入的数值均为整数