NNN個の点とN−2N-2N−2個の辺からなる、閉路を持たない単純グラフがある。
iii番目の辺は点ai,bia_{i} , b_{i}ai,biを結んでいる。
このグラフに対し、適当に辺を1つ加えることで、木を構成することができる。
木を構成するような辺の加え方は何通りあるか。
入力はすべて整数である。
NNN
a1a_{1}a1 b1b_{1}b1
...
aN−2a_{N-2}aN−2 bN−2b_{N-2}bN−2
計算結果を一行に出力せよ。
4 1 2 3 4
4
例えば点1、点4を結ぶ辺を追加することで、木を構成することができます。
11 1 6 2 7 3 8 4 9 5 10 6 11 7 1 9 3 10 4
30