Description

有一棵N个点的树

最开始时所有边都是蓝色

每次你可以选择一条所有边都是蓝色的路径，删除其中的某条边，然后将路径的两个端点之间连一条红色

不断这样操作后

问是否可以得到最后目标树的状态，目标树的边全是红色

Format

Input

第一行给出数字N 接下来N-1行描述最开始的树 再接下N-1行描述目标状态的树

2<=N<=1e5

Output

如题

Samples

3
1 2
2 3
1 3
3 2

YES

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

YES

Hint

对于样例1

找到路径1到3，删除1-2这条边，然后连接1-3，边为红色