問題文


個の点と個の辺からなる、閉路を持たない単純グラフがある。

番目の辺は点を結んでいる。

このグラフに対し、適当に辺を1つ加えることで、木を構成することができる。

木を構成するような辺の加え方は何通りあるか。

制約


入力


入力はすべて整数である。

...

出力


計算結果を一行に出力せよ。

サンプル


入力1
4
1 2
3 4
出力1
4

例えば点1、点4を結ぶ辺を追加することで、木を構成することができます。

入力2
11
1 6
2 7
3 8
4 9
5 10
6 11
7 1
9 3
10 4
出力2
30

Submit


Go (1.14)