T4 蚂蚁搬家

题目信息

时间限制: 5s

空间限制: 512M

输入文件: ants.in

输出文件: ants.out

题目描述

$n$ 只蚂蚁居住在巢穴中，巢穴有 $n$ 个房间，编号为 $1$ 到 $n$。房间之间有 $n-1$ 条道路连通，房间和道路构成一棵树。初始情况下，每条道路都是白色的。每个巢穴中都住着很多只蚂蚁。

蚂蚁们印刷了一份地图，地图上也有一棵 $n$ 个点 $n-1$ 条边的树，点标号 $1$ 到 $n$。然而，由于印刷错误，地图上的树和巢穴实际的结构没有什么关系。

现在蚂蚁们要进行一场搬家。搬家由任意多次以下操作组成：

每次操作选取两个在地图上相邻的点 $u,v$。然后蚂蚁们会尝试从 $u$ 沿着巢穴中实际最短路径走到 $v$，如果路上经过的每条道路都是白色的，那么蚂蚁们会再走一遍并在路上任选一条道路染成黑色。如果经过的道路中至少一条是黑色，则蚂蚁们不会进行任何额外操作。

问：经过充分多次操作后，是否有可能让所有的道路都变成黑色。

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示实际巢穴中有一条道路 $(u,v)$。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示地图中有一条边 $(u,v)$。

输出格式

YES 表示能全部染成黑色，NO 表示不能。

样例

样例输入 1

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

样例输出 1

YES

样例解释 1

实际地图是一条链 $1-2-3-4-5$。

一种染黑方案是：

• 走 $1$ 到 $5$，染黑边 $(4,5)$；
• 走 $1$ 到 $4$，染黑边 $(1,2)$；
• 走 $2$ 到 $4$，染黑边 $(2,3)$；
• 走 $3$ 到 $4$，染黑边 $(3,4)$；

样例输入 2

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

样例输出 2

NO

数据范围与提示

子任务捆绑测试。

对于所有数据，$1\le n\le 10^6$。

子任务 $1$ 占 $30\%$ 的分数，$n\le 10^3$；

子任务 $2$ 占 $30\%$ 的分数，$n\le 10^5$；

子任务 $3$ 占 $40\%$ 的分数，无特殊限制。