Ламінарія

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

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

Вам потрібно вибрати вершину \(u\) з дерева \(T_1\), вершину \(v\) з дерева \(T_2\) та з’єднати їх ребром. У результаті ви отримаєте нове дерево \(T\) з \(2n\) вершинами, у якому для кожного кольору від \(1\) до \(n\) є рівно дві вершини.

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

• Виберіть дві непозначені вершини одного кольору \(i\), після чого позначте всі внутрішні вершини на шляху між ними. Також позначте обидві вершини кольору \(i\).

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Обмеження

\(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

Примітки