В інформатиці NP-повні (NP-Complete, скорочено NPC) задачі становлять клас класичних задач, що поєднують теоретичну глибину та обчислювальну складність — на сьогодні для них не знайдено поліноміальних алгоритмів, але щойно будь-яку з цих задач буде подолано, усі задачі класу NP також будуть легко розв'язані.

Захоплений дослідженням алгоритмів маленький W завжди мріяв кинути виклик задачам NPC. Він дізнався, що знаменита в теорії графів «Задача про максимальний спільний індукований підграф» якраз є класичною задачею NPC. Зіткнувшись із нездоланною прірвою обчислювальної складності на загальних графах, маленький W вирішив зробити крок назад і почати з більш витончених за структурою дерев, щоб дослідити задачу про ізоморфні зв'язні підграфи на деревах.

А саме, задано два некореневі дерева $T_1$ і $T_2$, кожне з яких містить $n$ вершин, занумерованих від $1 \sim n$ відповідно. Маленький W хоче вибрати непорожню підмножину вершин $V_1$ у $T_1$ та непорожню підмножину вершин $V_2$ у $T_2$, зберігши всі початкові ребра відповідного дерева між вершинами всередині кожної множини, тим самим індукувавши два підграфи $G_1$ і $G_2$ відповідно.

Маленький W вимагає, щоб два індуковані підграфи $G_1, G_2$ одночасно задовольняли такі умови:

1. Зв'язність: і $G_1$, і $G_2$ є зв'язними графами (зокрема, граф, що містить лише $1$ вершину, також вважається зв'язним).
2. Ізоморфізм: $G_1$ і $G_2$ ізоморфні. Тобто існує бієкція (взаємно однозначна відповідність) $f : V_1 \to V_2$ із $V_1$ у $V_2$ така, що для будь-яких $u, v \in V_1$ вершини $u$ і $v$ з'єднані ребром у $G_1$ тоді й лише тоді, коли $f(u)$ і $f(v)$ з'єднані ребром у $G_2$. Примітка: відповідні одна одній вершини $u$ і $f(u)$ не зобов'язані мати однакові номери.

Тепер маленький W передає цю спрощену задачу вам: обчисліть, яку найбільшу кількість вершин можуть містити ізоморфні зв'язні підграфи, що задовольняють наведені вище вимоги (тобто знайдіть максимальне значення $|V_1|$)?

Вхідні дані

Вхідні дані зчитуються зі stdin.

Перший рядок містить одне додатне ціле число $n$ — кількість вершин у кожному дереві.

Наступні $n - 1$ рядків містять по два додатні цілі числа $u, v$, які описують неорієнтоване ребро $(u, v)$ в дереві $T_1$.

Наступні $n - 1$ рядків містять по два додатні цілі числа $u, v$, які описують неорієнтоване ребро $(u, v)$ в дереві $T_2$.

Вихідні дані

Виведіть відповідь у stdout.

Виведіть в одному рядку одне додатне ціле число — максимальну кількість вершин у вибраних ізоморфних зв'язних підграфах.

Приклади

Вхідні дані 1

4
1 2
2 3
3 4
1 2
1 3
1 4

Вихідні дані 1

3

Примітка

Виберемо в $T_1$ множину вершин $V_1 = \{1, 2, 3\}$, а в $T_2$ — множину вершин $V_2 = \{1, 2, 3\}$. Якщо зіставити вершинам $1, 2, 3$ із $V_1$ відповідно вершини $2, 1, 3$ із $V_2$, то обидва індуковані підграфи будуть ланцюгами з $3$ вершин, задовольняючи умови зв'язності та ізоморфізму.

Оскільки $T_1$ саме є ланцюгом, будь-який його зв'язний підграф також обов'язково є ланцюгом; водночас найдовший ланцюг у зірковому графі $T_2$ містить лише $3$ вершини, тому вибрати ізоморфні зв'язні підграфи з кількістю вершин більше $3$ неможливо.

Приклад 2

Див. файли npc/npc2.in та npc/npc2.ans у робочій директорії учасника.

Цей приклад задовольняє обмеження підзадачі $1$.

Приклад 3

Див. файли npc/npc3.in та npc/npc3.ans у робочій директорії учасника.

Цей приклад задовольняє обмеження підзадачі $4$.

Приклад 4

Див. файли npc/npc4.in та npc/npc4.ans у робочій директорії учасника.

Цей приклад задовольняє обмеження підзадачі $7$.

Підзадачі

У всіх тестових даних гарантується, що $1 \le n \le 500$, номери обох кінців кожного ребра лежать у межах $1 \sim n$, а обидва задані графи є коректними деревами.

Максимальний бал за цю задачу становить $150$ балів, використовується групове оцінювання за підзадачами. Бали за підзадачу нараховуються лише в разі проходження всіх тестів цієї підзадачі. Детальні обмеження для кожної підзадачі наведено в таблиці нижче.

Особлива властивість A: степені всіх вершин в обох деревах не перевищують $3$.

Особлива властивість B: існує оптимальний розв'язок, ізоморфне відображення якого переводить вершину $1$ дерева $T_1$ у вершину $1$ дерева $T_2$.

Особлива властивість C: гарантується, що підсумкова відповідь не менша за $n - 1$.

Примітка: степенем вершини в дереві називається кількість ребер, безпосередньо інцидентних цій вершині.