题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。此外，$N-1$ 条边中，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

初始情况下，所有边都被涂成蓝色。之后，高桥君将进行如下操作 $N-1$ 次，将这棵树转换为一棵红色的树：

• 从只包含蓝色边的路径中选择一条，从该路径上删去一条边。
• 随后，在一开始选的那条路径的两个端点之间添加一条红色的边。

最终，他希望得到一棵新的树，包含 $N$ 个顶点且满足下列性质：对于每个 $i$，存在一条红色的边直接连接顶点 $c_i$ 和顶点 $d_i$。

请判断高桥君能否完成这样的目标。

输入格式

输入从标准输入读入，格式如下：

$N$ $a_1$ $b_1$ … $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ … $c_{N-1}$ $d_{N-1}$

输出格式

如果高桥君能够将初始的树成功改造成目标树，则输出 YES。否则输出 NO。

样例 1

输入

3
1 2
2 3
1 3
3 2

输出

YES

样例 2

输入

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

输出

YES

样例 3

输入

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

输出

NO

说明/提示

约束条件

• $2 \leq N \leq 10^5$
• $1 \leq a_i, b_i, c_i, d_i \leq N$
• $a_i \neq b_i$
• $c_i \neq d_i$
• 输入给定的两组边分别构成一棵树。

样例解释 1

高桥君可以按照如下顺序构造目标红色树：

• 首先，选择连接顶点 $1$ 和 $3$ 的路径，并删去蓝色的边 $1-2$，再加入红色的边 $1-3$。
• 接着，选择连接顶点 $2$ 和 $3$ 的路径，并删去蓝色的边 $2-3$，再加入红色的边 $2-3$。

由 ChatGPT 5 翻译