F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 4754. -- [Jsoi2016]独特的树叶

4754: [Jsoi2016]独特的树叶

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 370  Solved: 168
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

1

HINT

Source

[Submit][Status][Discuss]

HOME Back