wwk与黑白树

题目限制

7000 ms 256 M

题目描述

$wowaka$ 给你一棵树，上面有 $n$ 个节点。一开始所有边都是黑色的。每次你可以选择树上一条所有边都是黑色的路径，删掉其中一条边，然后在路径的两个端点之间连一条白色的边。求最后能否得到目标形态（都是白色的边）的树。

输入格式

本题包含多组测试数据。第一行输入一个正整数T表示测试组数（1≤T≤10） 之后对于每组数据，第一行输入一个正整数n，表示树的节点数量；（2≤n≤50000） 之后n-1行，每行两个数a[i],b[i]，表示原树上a[i]与b[i]间有一条边； 之后n-1行，每行两个数c[i],d[i]，表示目标形态树上c[i]与d[i]间有一条边；

输出格式

输出T行，每行一个字符串表示答案。若可以得到则输出 "YES"，否则输出 "NO"。

数据范围

对于40%的数据，$2\le n \le 200$。

对于60%的数据，$2\le n \le 2000$。

对于100%的数据， $1\le T \le 10, 2\le n \le 5\times 10^4, 1 \le a[i],b[i],c[i],d[i] \le n, a[i]\ne b[i], c[i]\ne d[i]$，输入数据保证为一棵树。

输入样例

1
3
1 2
2 3
1 3
3 2

输出样例

YES