시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 256 MB74457.143%

문제

Given are trees $T_1$ and $T_2$. Each tree has $n$ vertices numbered from $1$ through $n$. Let $d(v, u, T)$ denote the number of edges on the path between vertices $v$ and $u$ in tree $T$. Calculate the following sum:

$$ \sum_{1 \le u < v \le n} \left(d(v, u, T_1) + d(v, u, T_2)\right)^2 \text{.} $$

As the answer may be large, find it modulo $2^{32}$.

입력

The first line contains one integer $n$: the number of vertices in each tree ($1 \le n \le 100\,000$).

Each of the next $n - 1$ lines contains two integers, $u$ and $v$, denoting an edge between vertices $u$ and $v$ in tree $T_1$ ($1 \le u, v \le n$).

Each of the last $n - 1$ lines contains two integers, $u$ and $v$, denoting an edge between vertices $u$ and $v$ in tree $T_2$ ($1 \le u, v \le n$).

출력

Print the answer modulo $2^{32}$.

예제 입력 1

3
1 2
1 3
1 2
1 3

예제 출력 1

24

예제 입력 2

3
1 2
1 3
1 2
2 3

예제 출력 2

22