Find the Extra Leaf in the Augmented Tree

JYY has two trees \(A\) and \(B\). Tree \(A\) has \(N\) nodes labeled from \(1\) to \(N\) and tree \(B\) has \(N+1\) nodes labeled from \(1\) to \(N+1\). It is known that tree \(B\) is obtained by taking tree \(A\), adding one extra leaf (i.e. a new node attached to an existing node) and then randomly permuting the node labels.

Your task is to determine which node in tree \(B\) corresponds to the extra leaf. In other words, if you remove this extra leaf from tree \(B\), the remaining tree will be isomorphic to tree \(A\).

Note: Two trees are isomorphic if one can be transformed into the other by renaming the vertices. A standard approach to test tree isomorphism is the AHU algorithm which computes a canonical form of the tree using a recursive encoding. For a rooted tree, if we define the encoding function as

[ \texttt{encode}(u) = (\text{sort}_{v \in children(u)}(\texttt{encode}(v))) ]

then the canonical form of the tree is the lexicographically smallest encoding taken over all choices of the center as the root.

inputFormat

The first line contains an integer \(N\), the number of nodes in tree \(A\). The next \(N-1\) lines each contain two integers \(u\) and \(v\), representing an edge in tree \(A\). The following \(N\) lines each contain two integers \(u\) and \(v\), representing an edge in tree \(B\). It is guaranteed that tree \(B\) is formed by adding a leaf to tree \(A\) and then permuting the node labels arbitrarily.

outputFormat

Output a single integer — the label of the extra leaf in tree \(B\>.

sample

2
1 2
2 3
2 1

1