[JSOI2016] 独特的树叶

题目描述

JYY有两棵树 $A$ 和 $B$ :树 $A$ 有 $N$ 个点,编号为 $1$ 到 $N$ ;树 $B$ 有$N+1$ 个节点,编号为 $1$ 到$N+1$ JYY 知道树 $B$ 恰好是由树 $A$ 加上一个叶节点,然后将节点的编号打乱后得到的。他想知道,这个多余的叶子到底是树 $B$ 中的哪一个叶节点呢?

输入输出格式

输入格式


输入一行包含一个正整数 $N$。 接下来 $N-1$ 行,描述树$ A$,每行包含两个整数表示树 $A$ 中的一条边; 接下来 $N$ 行,描述树 $B$,每行包含两个整数表示树 $B$ 中的一条边。

输出格式


输出一行一个整数,表示树 $B$ 中相比树 $A$ 多余的那个叶子的编号。如果有多个符合要求的叶子,输出 $B$ 中编号最小的那一个的编号。

输入输出样例

输入样例 #1

5
1 2
2 3
1 4
1 5
1 2
2 3
3 4
4 5
3 6

输出样例 #1

1

说明

对于所有数据,$1 \leq n \leq 10 ^ 5$