题目描述

给定一棵由 $N$ 个顶点编号为 $1$ 到 $N$ 的树。其中第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

初始状态下，每个边都被涂成蓝色。高桥将进行 $N-1$ 次操作，将蓝色树转化为红色树，操作规则如下：

• 选择一个只包含蓝色边的简单路径，并去除其中的一条边。
• 然后，在所选路径的两个端点之间引入一条新的红色边。

高桥的目标是使得树中存在一条红色边，该红色边连接着顶点 $c_i$ 和 $d_i$（对于每个 $i$）。

请确定是否可以实现这个目标。

约束条件

• $2 ≤ N ≤ 10^5$
• $1 ≤ a_i,b_i,c_i,d_i ≤ N$
• $a_i ≠ b_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

示例输出 1

YES

可以实现目标，如下所示：

• 首先，选择连接顶点 $1$ 和 $3$ 的路径，并移除蓝色边 $1-2$。然后引入一条新的红色边 $1-3$。
• 接着，选择连接顶点 $2$ 和 $3$ 的路径，并移除蓝色边 $2-3$。然后引入一条新的红色边 $2-3$。

示例输入 2

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

示例输出 2

YES

示例输入 3

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

示例输出 3

NO