P4323 [JSOI2016] Unique Leaf

JYY has two trees $A$ and $B$: tree $A$ has $N$ nodes labeled from $1$ to $N$; tree $B$ has $N + 1$ nodes labeled from $1$ to $N + 1$. JYY knows that tree $B$ is obtained from tree $A$ by adding one leaf node and then shuffling the node labels. He wants to determine which leaf node in tree $B$ is the extra one.

The first line contains a positive integer $N$. The next $N - 1$ lines describe tree $A$, each containing two integers that represent an edge of tree $A$. The next $N$ lines describe tree $B$, each containing two integers that represent an edge of tree $B$.

Output a single integer: the label in tree $B$ of the extra leaf compared to tree $A$. If multiple leaves satisfy the condition, output the smallest label among them.

For all testdata, $1 \leq N \leq 10^{5}$. Translated by ChatGPT 5