在計算機科學中，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 將這個簡化後的問題交給了你：請計算滿足上述要求的同構連通子圖最多可以包含多少個節點（即求 $|V_1|$ 的最大值）？

輸入格式

從 stdin 中讀入資料。

第一行包含一個正整數 $n$，表示每棵樹的節點數量。

接下來 $n - 1$ 行，每行包含兩個正整數 $u, v$，表示樹 $T_1$ 中的一條無向邊 $(u, v)$。

接下來 $n - 1$ 行，每行包含兩個正整數 $u, v$，表示樹 $T_2$ 中的一條無向邊 $(u, v)$。

輸出格式

輸出到 stdout。

輸出一行一個正整數，表示選出的同構連通子圖的最大節點數。

範例

輸入格式 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$，導出的兩個子圖均為包含 $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$。

註：樹中一個節點的度數是指與該節點直接相連的邊的數量。