给定两棵树 $T_1$ 和 $T_2$。每棵树都有 $n$ 个顶点，编号从 $1$ 到 $n$。令 $d(v, u, T)$ 表示树 $T$ 中顶点 $v$ 和 $u$ 之间路径上的边数。计算以下和：

$$\sum_{v=1}^{n} \sum_{u=1}^{n} (d(v, u, T_1) + d(v, u, T_2))^2$$

由于答案可能很大，请将其对 $2^{32}$ 取模。

输入格式

第一行包含一个整数 $n$：每棵树的顶点数 ($1 \le n \le 100\,000$)。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示树 $T_1$ 中顶点 $u$ 和 $v$ 之间的一条边 ($1 \le u, v \le n$)。

最后 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示树 $T_2$ 中顶点 $u$ 和 $v$ 之间的一条边 ($1 \le u, v \le n$)。

输出格式

输出答案对 $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