当前没有测试数据。

题目描述

Mike喜(tao)欢(yan)数据结构，尤其是树。

有一天，出题人给了Mike一棵树$T_{1}$，Mike觉得这棵树非常不优美，于是Mike把树通过一系列操作变成了树$T_{2}$。

Mike每次任意从$T_{1}$中选两个还联通的点$u,v$，在树$T_{2}$中加入边$(u,v)$，同时任意删除$T_{1}$中$(u,v)$路径上一条边。

过了很久，Mike已经不记得他每一步是怎么操作的，只记得最终得到的树的形态是$T_{2}$。

请你判断一下是否存在这样一种合法操作序列，使得Mike最终能得到树$T_{2}$，如果存在，输出"YES"，否则输出"NO"。

为了防止同学们采用期望得分超过$1$的随机输出答案算法，Mike决定采用多组数据，每个测试点共$T$组数据。

输入格式

第一行一个整数$T$，表示测试数据组数。

对于每组测试数据，第一行是一个整数$n$，表示点的个数。

接下来$n-1$行，每行两个整数$u,v$，表示树$T_{1}$中存在边$(u,v)$

接下来$n-1$行，每行两个整数$u,v$，表示树$T_{2}$中存在边$(u,v)$

输出格式

共$T$行，每行输出一个字符串，表示判定的结果。

样例1

ex_tree1.in

1
3
1 2
2 3
1 3
3 2

ex_tree1.ans

YES

样例2

ex_tree2.in

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

ex_tree2.ans

NO

数据范围

各测试点数据范围如下表：

测试点编号	$T$	$n$或$\sum n$范围	特殊条件
$1, 2$	$=4$	$n \leq 8$	无
$3, 4$	$=10$	$n \leq 16$
$5, 6$		$n \leq 1000$	$T_{1}$的边形如$(i,i+1)$
$7, 8$			$T_{1}$的边形如$(1,i)$
$9, 10, 11, 12$			无
$13, 14$		$\sum n \leq 10^{5}$	$T_{1}$的边形如$(i,i+1)$
$15, 16$			$T_{1}$的边形如$(1,i)$
$17, 18, 19$			无
$20$		$\sum n \leq 2*10^{5}$

经过Mike精心的计算，随机输出答案的算法期望得分不超过$1$分。

时间限制：1s

空间限制：256M

请注意常数因子对程序效率带来的影响。