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

Примітки