컴퓨터 과학에서 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$개의 줄에는 각각 트리 $T_1$의 무방향 간선 $(u, v)$를 나타내는 두 양의 정수 $u, v$가 주어진다.

그다음 $n - 1$개의 줄에는 각각 트리 $T_2$의 무방향 간선 $(u, v)$를 나타내는 두 양의 정수 $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$ 이상임이 보장된다.

참고: 트리에서 한 정점의 차수란 그 정점에 직접 연결된 간선의 개수를 뜻한다.