A92008.「JSOI2016」独特的树叶

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

JYY 有两棵树 AABB:树 AANN 个点,编号为 11NN;树 BBN+1N+1 个点,编号为 11N+1N+1

JYY 知道树 BB 恰好是由树 AA 加上一个叶节点,然后将节点的编号打乱后得到的。他想知道,这个多余的叶子到底是树 BB 中的哪一个叶节点呢?

输入格式

输入一行包含一个正整数 NN
接下来 N1N-1 行,描述树 AA,每行包含两个整数表示树 AA 中的一条边;
接下来 NN 行,描述树 BB,每行包含两个整数表示树 BB 中的一条边。

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    1

说明/提示

对于所有数据,1N1051 \leq N \leq 10^5

首页