题目描述

在计算机科学中，NP 完全（NP-Complete，简称 NPC）问题是一类兼具理论深度与求解难度的经典问题——目前尚未找到它们的多项式时间算法，但一旦其中任何一个问题被攻克，所有的 NP 问题都将迎刃而解。

热衷于算法研究的小 W 一直梦想着挑战 NPC 问题。他了解到，图论中著名的“最大公共诱导子图问题”正是经典的 NPC 问题。面对一般图上难以逾越的复杂度鸿沟，小 W 决定退一步，先从结构更为优美的树入手，研究树上的同构连通子图问题。

具体而言，给定两棵均包含 $n$ 个节点的无根树 $T_1$ 和 $T_2$，两棵树的节点均分别编号为 $1 \sim n$。小 W 希望在 $T_1$ 中选出一个非空节点子集 $V_1$，并在 $T_2$ 中选出一个非空节点子集 $V_2$，同时保留各自集合内部节点在原树中的所有原有边，从而分别导出两个子图 $G_1$ 和 $G_2$。

小 W 要求导出的两个子图 $G_1, G_2$ 必须同时满足：

1. 连通性：$G_1$ 和 $G_2$ 均为连通图（特别地，仅包含 $1$ 个节点的图也视为连通）。
2. 同构性：$G_1$ 与 $G_2$ 同构。即存在一个从 $V_1$ 到 $V_2$ 的双射（一一对应关系）$f: V_1 \to V_2$，使得对于任意 $u, v \in V_1$，$u$ 与 $v$ 在 $G_1$ 中有边相连，当且仅当 $f(u)$ 与 $f(v)$ 在 $G_2$ 中有边相连。注意：相互对应的节点 $u$ 和 $f(u)$ 不要求编号相同。

现在，小 W 将这个简化后的问题交给了你：请计算满足上述要求的同构连通子图最多可以包含多少个节点（即求 $\vert V_1\vert$ 的最大值）？

输入格式

从标准输入读入数据。

第一行包含一个正整数 $n$，表示每棵树的节点数量。

接下来 $n - 1$ 行，每行包含两个正整数 $u, v$，表示树 $T_1$ 中的一条无向边 $(u, v)$。

接下来 $n - 1$ 行，每行包含两个正整数 $u, v$，表示树 $T_2$ 中的一条无向边 $(u, v)$。

输出格式

输出到标准输出。

输出一行一个正整数，表示选出的同构连通子图的最大节点数。

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

3

提示

样例 1 解释

在 $T_1$ 中选择节点集合 $V_1 = \{1, 2, 3\}$，在 $T_2$ 中选择节点集合 $V_2 = \{1, 2, 3\}$。将 $V_1$ 中的节点 $1, 2, 3$ 依次对应到 $V_2$ 中的节点 $2, 1, 3$，导出的两个子图均为包含 $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：存在一种最优方案，其同构映射将 $T_1$ 的节点 $1$ 对应到 $T_2$ 的节点 $1$。

特殊性质 C：保证最终答案不小于 $n - 1$。

注：树中一个节点的度数是指与该节点直接相连的边的数量。