Two Trees

Time limit8sMemory limit256 MB

Summary

Given two trees on the same n vertices, compute the sum over all vertex pairs of the squared sum of their distances in both trees, modulo 2^32.

Level: Hard8 of 10
Topics: Tree, Divide and conquer, Math
Solved: No attempts yet

Problem

Trees $T_1$ and $T_2$ are given. Each tree has $n$ vertices numbered from $1$ through $n$ . Let $d(v, u, T)$ be the number of edges on the path between vertices $v$ and $u$ in tree $T$ . Compute the following sum.

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

The answer may be large, so print it modulo $2^{32}$ .

Input

The first line contains one integer $n$ , the number of vertices in each tree ( $1 \le n \le 100000$ ). Each of the next $n-1$ lines contains two integers $u$ and $v$ , an edge between $u$ and $v$ in $T_1$ ( $1 \le u, v \le n$ ). Each of the last $n-1$ lines contains two integers $u$ and $v$ , an edge between $u$ and $v$ in $T_2$ ( $1 \le u, v \le n$ ).

Output

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

Examples2

Example 1
Input
```
3
1 2
1 3
1 2
1 3
```
Expected output
```
24
```
Example 2
Input
```
3
1 2
1 3
1 2
2 3
```
Expected output
```
22
```