En ciencias de la computación, los problemas NP-Completos (NP-Complete, abreviados como NPC) son una clase de problemas clásicos que combinan profundidad teórica y dificultad de resolución: hasta ahora no se ha encontrado ningún algoritmo de tiempo polinomial para ellos, pero una vez que cualquiera de estos problemas sea conquistado, todos los problemas NP quedarán resueltos.

El pequeño W, apasionado por la investigación de algoritmos, siempre ha soñado con desafiar los problemas NPC. Supo que el famoso «Problema del subgrafo inducido común máximo» en teoría de grafos es precisamente un problema NPC clásico. Ante la brecha de complejidad insuperable en grafos generales, el pequeño W decidió dar un paso atrás y comenzar por los árboles, que tienen una estructura más elegante, para estudiar el problema de los subgrafos conexos isomorfos en árboles.

Específicamente, se dan dos árboles sin raíz $T_1$ y $T_2$, cada uno con $n$ nodos numerados respectivamente de $1 \sim n$. El pequeño W desea seleccionar un subconjunto no vacío de nodos $V_1$ en $T_1$ y un subconjunto no vacío de nodos $V_2$ en $T_2$, conservando todas las aristas originales en el árbol respectivo entre los nodos dentro de cada conjunto, induciendo así dos subgrafos $G_1$ y $G_2$, respectivamente.

El pequeño W exige que los dos subgrafos inducidos $G_1, G_2$ cumplan simultáneamente:

1. Conectividad: Tanto $G_1$ como $G_2$ son grafos conexos (en particular, un grafo que contiene solo $1$ nodo también se considera conexo).
2. Isomorfismo: $G_1$ y $G_2$ son isomorfos. Es decir, existe una biyección (correspondencia uno a uno) $f : V_1 \to V_2$ de $V_1$ a $V_2$ tal que, para cualesquiera $u, v \in V_1$, $u$ y $v$ están conectados por una arista en $G_1$ si y solo si $f(u)$ y $f(v)$ están conectados por una arista en $G_2$. Nota: No se requiere que los nodos correspondientes $u$ y $f(u)$ tengan el mismo número.

Ahora, el pequeño W te entrega este problema simplificado: por favor, calcula cuántos nodos como máximo pueden contener los subgrafos conexos isomorfos que cumplen los requisitos anteriores (es decir, halla el valor máximo de $|V_1|$).

Entrada

Lee los datos desde stdin.

La primera línea contiene un entero positivo $n$, que representa la cantidad de nodos en cada árbol.

Las siguientes $n - 1$ líneas contienen cada una dos enteros positivos $u, v$, que representan una arista no dirigida $(u, v)$ en el árbol $T_1$.

Las siguientes $n - 1$ líneas contienen cada una dos enteros positivos $u, v$, que representan una arista no dirigida $(u, v)$ en el árbol $T_2$.

Salida

Escribe la salida en stdout.

Imprime una línea con un entero positivo, que representa el número máximo de nodos de los subgrafos conexos isomorfos seleccionados.

Ejemplos

Entrada 1

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

Salida 1

3

Nota

En $T_1$ se selecciona el conjunto de nodos $V_1 = \{1, 2, 3\}$ y en $T_2$ se selecciona el conjunto de nodos $V_2 = \{1, 2, 3\}$. Al hacer corresponder los nodos $1, 2, 3$ de $V_1$ respectivamente con los nodos $2, 1, 3$ de $V_2$, los dos subgrafos inducidos son cadenas que contienen $3$ nodos, cumpliendo con ser conexos e isomorfos.

Dado que $T_1$ es en sí mismo una cadena, cualquier subgrafo conexo suyo también debe ser necesariamente una cadena; mientras que la cadena más larga en el grafo estrella $T_2$ contiene solo $3$ nodos, por lo que es imposible seleccionar subgrafos conexos isomorfos con más de $3$ nodos.

Ejemplo 2

Consulta npc/npc2.in y npc/npc2.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de la subtarea $1$.

Ejemplo 3

Consulta npc/npc3.in y npc/npc3.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de la subtarea $4$.

Ejemplo 4

Consulta npc/npc4.in y npc/npc4.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de la subtarea $7$.

Subtareas

Para todos los datos, se garantiza que $1 \le n \le 500$, los números de ambos extremos de cada arista están entre $1 \sim n$, y los dos grafos dados son árboles válidos.

La puntuación máxima de este problema es de $150$ puntos y se utiliza evaluación agrupada por subtareas. Solo obtendrás la puntuación de una subtarea si superas todos los casos de prueba de dicha subtarea. Los rangos de datos detallados de cada subtarea se muestran en la siguiente tabla.

Propiedad especial A: El grado de todos los nodos en ambos árboles no supera $3$.

Propiedad especial B: Existe una solución óptima cuyo mapeo isomorfo hace corresponder el nodo $1$ de $T_1$ con el nodo $1$ de $T_2$.

Propiedad especial C: Se garantiza que la respuesta final no es menor que $n - 1$.

Nota: El grado de un nodo en un árbol se refiere a la cantidad de aristas conectadas directamente a dicho nodo.