Laminaria

Обмеження: 5 сек., 1024 МіБ

You are given two trees $T_1$ and $T_2$ of $n$ vertices. In both trees, the vertices are numbered $1$ through $n$. Also, in both trees, the $i$-th vertex has color $i$ for all $1 \le i \le n$.

You want to choose a vertex $u$ from $T_1$, a vertex $v$ from $T_2$, and connect them with an edge. This way, you will obtain a new tree $T$ of $2 n$ vertices with two vertices of each color from $1$ to $n$.

Then, you will perform the following operation of marking vertices of $T$. Initially, all vertices are not marked.

• Choose two vertices of the same color $i$ that are not marked, and all internal vertices on the path between them are marked. Mark both vertices of color $i$.

We call a tree $T$ a laminaria if it is possible to mark all its vertices applying the above operation any number of times.

In how many ways can you connect $T_1$ and $T_2$ to obtain a laminaria?

Вхідні дані

The first line contains an integer $n$ – the number of vertices in both given trees.

The following $n - 1$ lines contain two integers $u_i, v_i$ each – the ends of the $i$-th edge in $T_1$.

The following $n - 1$ lines contain the edges of $T_2$ in the same format.

Вихідні дані

Print a single integer – the number of ways to connect $T_1$ and $T_2$ to obtain a laminaria.

Обмеження

$1 \le n \le 2 \cdot 10^5$,

$1 \le u_i, v_i \le n$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 3 1 2 4 2 5 1 2 1 2 2 3 3 5 5 4	2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 2 3 3 4 1 2 2 3 3 4	4

Примітки