注意

C 問題と D 問題は問題設定および制約は同じで、実行時間制限のみが異なります。

本問題（C 問題）の実行時間制限は 10000 ms です。

問題文

$N$ 頂点の木 $A$ が与えられます。$A$ の頂点には $1,2,\dots ,N$ の番号がついており、$i=1,2,\dots, N-1$ について $i$ 番目の辺は $A$ の頂点 $u_i,v_i$ を結んでいます。

木 $A$ の $2$ つの頂点 $p,q$ の距離を $d_A(p,q)$ とします。

さらに $N$ 頂点の木 $B$ が与えられます。$B$ の頂点にも $1,2,\dots ,N$ の番号がついており、$j=1,2,\dots, N-1$ について $j$ 番目の辺は $B$ の頂点 $x_j,y_j$ を結んでいます。

木 $B$ の $2$ つの頂点 $p,q$ の距離を $d_B(p,q)$ とします。 $$\sum_{p=1}^{N}\sum_{q=1}^{N}d_A(p,q)d_B(p,q)$$ を $2^{64}$ で割ったあまりを求めてください。

制約

• $2\le N\le 2\times 10^5$
• $1\le u_i,v_i,x_j,y_j\le N$
• $A,B$ はそれぞれ与えられた辺によって木をなす。

入力

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{N-1}$ $y_{N-1}$

出力

答えを一行に出力してください。

サンプル

4
1 2
1 3
1 4
1 2
2 3
3 4

28

5
1 2
1 3
2 4
3 5
5 4
4 3
4 2
3 1

68