En informatique, les problèmes NP-complets (NP-Complete, abrégés en NPC) constituent une classe de problèmes classiques alliant profondeur théorique et difficulté de résolution — aucun algorithme en temps polynomial n'a encore été trouvé pour les résoudre, mais dès que l'un d'entre eux sera vaincu, tous les problèmes NP seront résolus du même coup.

Passionné par la recherche algorithmique, Petit W a toujours rêvé de défier les problèmes NPC. Il a appris que le célèbre « problème du sous-graphe induit commun maximum » en théorie des graphes est justement un problème NPC classique. Face au fossé de complexité insurmontable sur les graphes généraux, Petit W a décidé de faire un pas en arrière et de commencer par les arbres, dont la structure est plus élégante, afin d'étudier le problème des sous-graphes connexes isomorphes sur les arbres.

Plus précisément, on vous donne deux arbres non enracinés $T_1$ et $T_2$ contenant chacun $n$ nœuds, les nœuds des deux arbres étant respectivement numérotés de $1 \sim n$. Petit W souhaite sélectionner un sous-ensemble non vide de nœuds $V_1$ dans $T_1$ et un sous-ensemble non vide de nœuds $V_2$ dans $T_2$, tout en conservant toutes les arêtes d'origine dans l'arbre correspondant entre les nœuds internes à chaque ensemble, induisant ainsi respectivement deux sous-graphes $G_1$ et $G_2$.

Petit W exige que les deux sous-graphes induits $G_1, G_2$ vérifient simultanément :

1. Connexité : $G_1$ et $G_2$ sont tous deux des graphes connexes (en particulier, un graphe ne contenant que $1$ nœud est également considéré comme connexe).
2. Isomorphisme : $G_1$ et $G_2$ sont isomorphes. C'est-à-dire qu'il existe une bijection (correspondance biunivoque) $f : V_1 \to V_2$ de $V_1$ vers $V_2$ telle que, pour tous $u, v \in V_1$, $u$ et $v$ sont reliés par une arête dans $G_1$ si et seulement si $f(u)$ et $f(v)$ sont reliés par une arête dans $G_2$. Attention : les nœuds correspondants $u$ et $f(u)$ ne sont pas tenus d'avoir le même numéro.

Maintenant, Petit W vous confie ce problème simplifié : veuillez calculer le nombre maximum de nœuds que peuvent contenir des sous-graphes connexes isomorphes satisfaisant aux exigences ci-dessus (c'est-à-dire trouver la valeur maximale de $|V_1|$) ?

Entrée

Lire les données depuis stdin.

La première ligne contient un entier strictement positif $n$, représentant le nombre de nœuds de chaque arbre.

Les $n - 1$ lignes suivantes contiennent chacune deux entiers strictement positifs $u, v$, représentant une arête non orientée $(u, v)$ dans l'arbre $T_1$.

Les $n - 1$ lignes suivantes contiennent chacune deux entiers strictement positifs $u, v$, représentant une arête non orientée $(u, v)$ dans l'arbre $T_2$.

Sortie

Écrire la sortie sur stdout.

Afficher une seule ligne contenant un entier strictement positif, représentant le nombre maximum de nœuds des sous-graphes connexes isomorphes sélectionnés.

Exemples

Entrée 1

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

Sortie 1

3

Remarque

En choisissant l'ensemble de nœuds $V_1 = \{1, 2, 3\}$ dans $T_1$ et l'ensemble de nœuds $V_2 = \{1, 2, 3\}$ dans $T_2$, et en associant successivement les nœuds $1, 2, 3$ de $V_1$ aux nœuds $2, 1, 3$ de $V_2$, les deux sous-graphes induits sont tous deux des chaînes contenant $3$ nœuds, ce qui satisfait la connexité et l'isomorphisme.

Comme $T_1$ est lui-même une chaîne, tout sous-graphe connexe de $T_1$ est nécessairement une chaîne ; or, la plus longue chaîne dans le graphe étoile $T_2$ ne contient que $3$ nœuds, il est donc impossible de sélectionner des sous-graphes connexes isomorphes comportant plus de $3$ nœuds.

Exemple 2

Voir npc/npc2.in et npc/npc2.ans dans le répertoire du candidat.

Cet exemple satisfait aux contraintes de la sous-tâche $1$.

Exemple 3

Voir npc/npc3.in et npc/npc3.ans dans le répertoire du candidat.

Cet exemple satisfait aux contraintes de la sous-tâche $4$.

Exemple 4

Voir npc/npc4.in et npc/npc4.ans dans le répertoire du candidat.

Cet exemple satisfait aux contraintes de la sous-tâche $7$.

Sous-tâches

Pour l'ensemble des données, il est garanti que $1 \le n \le 500$, que les numéros des deux extrémités de chaque arête sont compris entre $1 \sim n$, et que les deux graphes donnés sont des arbres valides.

Le score total de ce problème est de $150$ points, avec une évaluation groupée par sous-tâches. Vous n'obtiendrez les points d'une sous-tâche que si vous réussissez tous les cas de test de cette sous-tâche. Les contraintes détaillées de chaque sous-tâche sont indiquées dans le tableau ci-dessous.

Propriété particulière A : Le degré de tous les nœuds dans les deux arbres ne dépasse pas $3$.

Propriété particulière B : Il existe une solution optimale dont l'application d'isomorphisme associe le nœud $1$ de $T_1$ au nœud $1$ de $T_2$.

Propriété particulière C : Il est garanti que la réponse finale est au moins $n - 1$.

Note : Le degré d'un nœud dans un arbre désigne le nombre d'arêtes directement reliées à ce nœud.