Ламінарія#12965

Ламінарія

Вам задано два дерева T_1 та T_2, кожне з яких має вершин. В обох деревах вершини пронумеровані від до . Крім того, в обох деревах вершина з номером має колір для всіх 1 \le i \le n.

Вам потрібно вибрати вершину з дерева T_1, вершину з дерева T_2 та з’єднати їх ребром. У результаті ви отримаєте нове дерево з вершинами, у якому для кожного кольору від до є рівно дві вершини.

Після цього ви будете виконувати таку операцію позначення вершин дерева . Спочатку всі вершини є непозначеними.

Називатимемо дерево ламінарією, якщо можливо позначити всі його вершини, виконавши описану вище операцію довільну кількість разів.

Скількома способами можна з’єднати T_1 та T_2, щоб отримати ламінарію?

Input

У першому рядку задано ціле число — кількість вершин у кожному з двох заданих дерев.

У наступних n - 1 рядках задано по два цілі числа u_i, v_i — кінці -го ребра дерева T_1.

У наступних n - 1 рядках задано ребра дерева T_2 у такому самому форматі.

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

1 \le u_i, v_i \le n.

Output

Виведіть одне ціле число — кількість способів з’єднати T_1 та T_2 так, щоб отримати ламінарію.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

У першому прикладі можна з’єднати дві вершини кольору , щоб отримати ламінарію. Якщо вибирати кольори в порядку 1, 2, 3, 5, 4, то будуть позначені всі вершини. Проте це не єдиний спосіб отримати ламінарію. Інший спосіб — з’єднати дві вершини кольору . Загальна кількість способів отримати ламінарію дорівнює .