Laminaria

Limits: 5 sec., 1024 MiB

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?

Input

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.

Output

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

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le u_i, v_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
5 3 1 2 4 2 5 1 2 1 2 2 3 3 5 5 4	2

Input (stdin) сopy	Output (stdout) сopy
4 1 2 2 3 3 4 1 2 2 3 3 4	4

Notes