题目描述

树A有N个点，编号1..N；树B有N+1个点，编号1..N+1。保证B是给A增加一个叶节点后再任意重编号得到的。

请在B中删除一个叶节点及其关联边，使剩余树与A无标号同构：存在顶点之间的双射，使两点相邻当且仅当对应的两点相邻。输出可删除叶子的最小原编号。

输入

第一行N。接下来N-1行给A的边，随后N行给B的边，每行两个端点编号。两张图都保证是简单无向连通树。1≤N≤100000。

输出

一行满足要求的叶子的最小编号。叶子定义为度1；当A仅有一个点时，B的两个点都可删除。保证至少有一个答案。

输入样例

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

输出样例

1

本地整理说明

依据一本通公开题面整理，仅显式展开“打乱编号”的无标号同构定义及单点边界，保留原目标、完整规模和样例；不是官方原版评测数据。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：仅展开打乱编号即无标号同构、两图保证为树以及N=1边界；目标、范围、输出不改。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1695。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。