喺計算機科學入面，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$。

註：樹入面一個節點嘅度數係指同該節點直接相連嘅邊嘅數量。