A6321. 「JSOI2016」独特的树叶
编程题
省选/NOI-
知识点
题目描述
JYY 有两棵树 $A$ 和 $B$：树 $A$ 有 $N$ 个点，编号为 $1$ 到 $N$；树 $B$ 有 $N+1$ 个点，编号为 $1$ 到 $N+1$。
JYY 知道树 $B$ 恰好是由树 $A$ 加上一个叶节点，然后将节点的编号打乱后得到的。他想知道，这个多余的叶子到底是树 $B$ 中的哪一个叶节点呢？
JYY 知道树 $B$ 恰好是由树 $A$ 加上一个叶节点，然后将节点的编号打乱后得到的。他想知道，这个多余的叶子到底是树 $B$ 中的哪一个叶节点呢？
输入格式
输入一行包含一个正整数 $N$。
接下来 $N-1$ 行，描述树 $A$，每行包含两个整数表示树 $A$ 中的一条边；
接下来 $N$ 行，描述树 $B$，每行包含两个整数表示树 $B$ 中的一条边。
接下来 $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$。