 Competitions

Binary matching

You are given two binary trees and your task is to find their largest rooted isomorphic subtrees.

Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes.

Subtree is a tree that was obtained from the original one by continuously deleting some, possibly zero, leaf nodes.

Input

The first line contains the only positive integer n (1n1000) - number of nodes.

Each of the following (n - 1) lines contains a description of the tree edges, represented as two positive integers u, v (1u, v1000) Then follows a description of the second tree in the same format.

In both trees node with index 1 is a root node.

Output

Output a single positive integer - number of vertices in the larges rooted isomorphic subtree of given trees.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5
1 2
2 3
3 4
3 5
6
1 2
1 3
3 4
4 5
4 6
Output example #1
5
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem C