В информатике 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$.

Примечание: степенью вершины в дереве называется количество рёбер, непосредственно инцидентных этой вершине.