Вам задано два дерева T_1 та T_2, кожне з яких має вершин. В обох деревах вершини пронумеровані від до . Крім того, в обох деревах вершина з номером має колір для всіх 1 \le i \le n.
Вам потрібно вибрати вершину з дерева T_1, вершину з дерева T_2 та з’єднати їх ребром. У результаті ви отримаєте нове дерево з вершинами, у якому для кожного кольору від до є рівно дві вершини.
Після цього ви будете виконувати таку операцію позначення вершин дерева . Спочатку всі вершини є непозначеними.
Виберіть дві непозначені вершини одного кольору такі, що всі внутрішні вершини на шляху між ними вже позначені. Після цього позначте обидві вершини кольору .
Називатимемо дерево ламінарією, якщо можливо позначити всі його вершини, виконавши описану вище операцію довільну кількість разів.
Скількома способами можна з’єднати T_1 та T_2, щоб отримати ламінарію?
У першому рядку задано ціле число — кількість вершин у кожному з двох заданих дерев.
У наступних 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.
Виведіть одне ціле число — кількість способів з’єднати T_1 та T_2 так, щоб отримати ламінарію.
Example
Example 1
У першому прикладі можна з’єднати дві вершини кольору , щоб отримати ламінарію. Якщо вибирати кольори в порядку 1, 2, 3, 5, 4, то будуть позначені всі вершини. Проте це не єдиний спосіб отримати ламінарію. Інший спосіб — з’єднати дві вершини кольору . Загальна кількість способів отримати ламінарію дорівнює .