A92008.「JSOI2016」独特的树叶
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
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≤N≤105。