計算機科学において、NP 完全（NP-Complete、略称 NPC）問題は、理論的な深さと求解の難しさを兼ね備えた古典的な問題群です。現在までにこれらに対する多項式時間アルゴリズムは見つかっていませんが、もしそのうちのいずれか一つでも攻略されれば、すべての NP 問題が解決されることになります。

アルゴリズム研究に情熱を注ぐ小 W は、かねてから NPC 問題への挑戦を夢見ていました。彼は、グラフ理論で有名な「最大共通誘導部分グラフ問題」がまさに古典的な NPC 問題であることを知りました。一般グラフにおける乗り越えがたい計算量の壁を前に、小 W は一歩引き、まずはより美しい構造を持つ木から着手し、木上の同型連結部分グラフ問題を研究することにしました。

具体的には、ともに $n$ 個の頂点を含む 2 つの無根木 $T_1$ と $T_2$ が与えられます。どちらの木の頂点もそれぞれ $1 \sim n$ の番号が付けられています。小 W は $T_1$ から空でない頂点部分集合 $V_1$ を選び、$T_2$ から空でない頂点部分集合 $V_2$ を選び、それぞれの集合内部の頂点間にある元の木でのすべての辺を残すことで、2 つの部分グラフ $G_1$ と $G_2$ をそれぞれ誘導したいと考えています。

小 W は、誘導された 2 つの部分グラフ $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 はこの簡略化された問題をあなたに託しました。上記の要求を満たす同型連結部分グラフには最大で何個の頂点を含めることができるか（すなわち $|V_1|$ の最大値）を求めてください。

入力

stdin からデータを読み込む。

1 行目には、各木の頂点数を表す正の整数 $n$ が与えられる。

続く $n - 1$ 行には、それぞれ木 $T_1$ の無向辺 $(u, v)$ を表す 2 つの正の整数 $u, v$ が与えられる。

さらに続く $n - 1$ 行には、それぞれ木 $T_2$ の無向辺 $(u, v)$ を表す 2 つの正の整数 $u, v$ が与えられる。

出力

stdout に出力する。

選ばれた同型連結部分グラフの最大頂点数を表す正の整数を 1 行で出力せよ。

入出力例

入力 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\}$ を選ぶ。$V_1$ の頂点 $1, 2, 3$ を順に $V_2$ の頂点 $2, 1, 3$ に対応させると、誘導される 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$ の範囲内にあり、与えられる 2 つのグラフはいずれも正当な木であることが保証される。

本問題の満点は $150$ 点であり、小課題ごとのバンドルテストを採用している。ある小課題に含まれるすべてのテストケースに正解した場合にのみ、その小課題の得点が与えられる。各小課題の詳細な制約は以下の表の通りである。

特殊な性質 A：2 つの木のすべての頂点の次数は $3$ 以下である。

特殊な性質 B：同型写像が $T_1$ の頂点 $1$ を $T_2$ の頂点 $1$ に対応させるような最適解が存在する。

特殊な性質 C：最終的な答えが $n - 1$ 以上であることが保証される。

注：木における頂点の次数とは、その頂点に直接接続している辺の本数を指す。