W informatyce problemy NP-zupełne (NP-Complete, w skrócie NPC) stanowią klasę klasycznych problemów łączących głębię teoretyczną z trudnością obliczeniową — dotychczas nie znaleziono dla nich algorytmu działającego w czasie wielomianowym, ale gdy tylko którykolwiek z tych problemów zostanie pokonany, wszystkie problemy NP zostaną z łatwością rozwiązane.

Zafascynowany badaniami nad algorytmami Mały W od zawsze marzył o rzuceniu wyzwania problemom NPC. Dowiedział się, że słynny w teorii grafów „Problem maksymalnego wspólnego podgrafu indukowanego” jest właśnie klasycznym problemem NPC. W obliczu nieprzekraczalnej przepaści złożoności dla grafów ogólnych Mały W postanowił zrobić krok w tył i zacząć od drzew, które mają znacznie bardziej elegancką strukturę, aby zbadać problem izomorficznych spójnych podgrafów na drzewach.

Dokładniej, dane są dwa nieukorzenione drzewa $T_1$ oraz $T_2$, z których każde zawiera $n$ wierzchołków ponumerowanych odpowiednio od $1 \sim n$. Mały W chce wybrać niepusty podzbiór wierzchołków $V_1$ w drzewie $T_1$ oraz niepusty podzbiór wierzchołków $V_2$ w drzewie $T_2$, zachowując wszystkie oryginalne krawędzie z wyjściowych drzew pomiędzy wierzchołkami wewnątrz każdego ze zbiorów, indukując w ten sposób odpowiednio dwa podgrafy $G_1$ oraz $G_2$.

Mały W wymaga, aby oba indukowane podgrafy $G_1, G_2$ spełniały jednocześnie następujące warunki:

1. Spójność: Zarówno $G_1$, jak i $G_2$ są grafami spójnymi (w szczególności graf zawierający tylko $1$ wierzchołek również uznaje się za spójny).
2. Izomorfizm: Grafy $G_1$ i $G_2$ są izomorficzne. Oznacza to, że istnieje bijekcja (odpowiedniość wzajemnie jednoznaczna) $f : V_1 \to V_2$ ze zbioru $V_1$ na zbiór $V_2$ taka, że dla dowolnych $u, v \in V_1$ wierzchołki $u$ i $v$ są połączone krawędzią w $G_1$ wtedy i tylko wtedy, gdy $f(u)$ i $f(v)$ są połączone krawędzią w $G_2$. Uwaga: Odpowiadające sobie wierzchołki $u$ oraz $f(u)$ nie muszą mieć tych samych numerów.

Teraz Mały W przekazuje ten uproszczony problem Tobie: oblicz, ile maksymalnie wierzchołków mogą zawierać izomorficzne spójne podgrafy spełniające powyższe wymagania (tj. wyznacz maksymalną możliwą wartość $|V_1|$)?

Wejście

Dane należy wczytać ze standardowego wejścia stdin.

Pierwszy wiersz zawiera jedną dodatnią liczbę całkowitą $n$, oznaczającą liczbę wierzchołków w każdym drzewie.

Kolejne $n - 1$ wierszy zawiera po dwie dodatnie liczby całkowite $u, v$, oznaczające nieskierowaną krawędź $(u, v)$ w drzewie $T_1$.

Kolejne $n - 1$ wierszy zawiera po dwie dodatnie liczby całkowite $u, v$, oznaczające nieskierowaną krawędź $(u, v)$ w drzewie $T_2$.

Wyjście

Wynik należy wypisać na standardowe wyjście stdout.

Wypisz jeden wiersz zawierający jedną dodatnią liczbę całkowitą, oznaczającą maksymalną liczbę wierzchołków wybranych izomorficznych spójnych podgrafów.

Przykład

Wejście 1

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

Wyjście 1

3

Uwagi

Wybierzmy w $T_1$ zbiór wierzchołków $V_1 = \{1, 2, 3\}$, a w $T_2$ zbiór wierzchołków $V_2 = \{1, 2, 3\}$. Przyporządkowując wierzchołki $1, 2, 3$ ze zbioru $V_1$ kolejno wierzchołkom $2, 1, 3$ ze zbioru $V_2$, otrzymujemy dwa podgrafy indukowane będące ścieżkami złożonymi z $3$ wierzchołków, które są zarazem spójne i izomorficzne.

Ponieważ $T_1$ samo w sobie jest ścieżką, każdy jego spójny podgraf również musi być ścieżką; z kolei najdłuższa ścieżka w grafie gwiaździstym $T_2$ zawiera tylko $3$ wierzchołki, więc nie da się wybrać izomorficznych spójnych podgrafów o liczbie wierzchołków większej niż $3$.

Przykład 2

Zobacz pliki npc/npc2.in oraz npc/npc2.ans w katalogu zawodnika.

Ten przykład spełnia ograniczenia podzadania $1$.

Przykład 3

Zobacz pliki npc/npc3.in oraz npc/npc3.ans w katalogu zawodnika.

Ten przykład spełnia ograniczenia podzadania $4$.

Przykład 4

Zobacz pliki npc/npc4.in oraz npc/npc4.ans w katalogu zawodnika.

Ten przykład spełnia ograniczenia podzadania $7$.

Podzadania

Dla wszystkich danych testowych gwarantowane jest, że $1 \le n \le 500$, numery obu końców każdej krawędzi mieszczą się w przedziale $1 \sim n$, a oba podane grafy są poprawnymi drzewami.

Maksymalny wynik za to zadanie wynosi $150$ punktów i obowiązuje testowanie pakietowe w podzadaniach. Punkty za dane podzadanie otrzymasz tylko wtedy, gdy Twój program przejdzie pomyślnie wszystkie testy w tym podzadaniu. Szczegółowe zakresy danych dla poszczególnych podzadań przedstawiono w poniższej tabeli.

Własność specjalna A: Stopień każdego wierzchołka w obu drzewach nie przekracza $3$.

Własność specjalna B: Istnieje rozwiązanie optymalne, którego izomorfizm przyporządkowuje wierzchołek $1$ drzewa $T_1$ wierzchołkowi $1$ drzewa $T_2$.

Własność specjalna C: Gwarantowane jest, że ostateczna odpowiedź jest nie mniejsza niż $n - 1$.

Uwaga: Stopień wierzchołka w drzewie oznacza liczbę krawędzi bezpośrednio połączonych z tym wierzchołkiem.