$N$頂点の木がある。各頂点はそれぞれ1から$N$の番号が割り振られている。
Gacho君と川林君はこの木を使って陣取りゲームをすることにした。
ゲームはGacho君と川林君が異なる頂点にいる状態からスタートする。
Gacho君から交互に頂点を移動することを繰り返し、最初に移動できなくなった方が負けである。
移動方法:
頂点$x$にいる時、頂点$x$と辺で直接結ばれているまだ誰も訪れたことがない頂点のいずれかに移動する。
そのような頂点が存在しない場合、移動することはできない。
Gacho君が最初にいる頂点を頂点$A$、川林君が最初にいる頂点を頂点$B$とする。
Gacho君と川林君が互いに最善を尽くしたとき、Gacho君が勝つことになる頂点$A$と頂点$B$の組み合わせの通り数を求めよ。
入力は以下の形式で与えられる。
$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$
入力はすべて整数で与えられる。
1行目に頂点数$N$が与えられる。
2行目から続く$N-1$行に木の辺の情報が空白区切りで与えられる。
$1+i$行目の入力は頂点$u_i$と頂点$v_i$が辺で結ばれていることを表す。
入力は以下の条件を満たす。
Gacho君が勝つ頂点$A$と頂点$B$の組み合わせの通り数を1行に出力せよ。
2 1 2
0
頂点$A$と頂点$B$の組み合わせは(1, 2), (2, 1)の2通りあり、どちらもGacho君は初手で移動することができないので必ず負ける。
6 1 2 2 3 3 4 4 5 5 6
12
5 1 2 1 3 3 4 3 5
12
20 14 1 2 1 18 14 10 1 12 10 5 1 17 5 7 1 11 17 4 1 19 2 15 1 3 19 8 15 9 8 20 8 6 1 16 15 13 7
243