该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师有一棵无向树，包含 $n$ 个节点，由 $n - 1$ 条边连接，所有边的边权值都为 $1$。

徐老师规定了一种操作—— 消除。

一次 消除 需要先选定树上的一条 路径，设路径两端分别为 $u,v$，路径上一共包含 $x$ 个节点。

若这条路径上的边权总和为 $x-1$，即可对这条路径进行 消除

消除 操作的效果是： 删除 这条路径上的 一条边，然后新增一条边权为 $0$ 的边，连接 $u,v$ 两个端点。

现在徐老师想知道，对于给定的一棵树 $S$，能否通过若干次 消除 操作，使得这棵树变成一棵仅包含边权为 $0$ 的边的树 $T$（$S$ 和 $T$ 的形态会提前给定）

输入格式

题目包含多组测试数据，输入第一行包含一个整数 $T$，表示数据数量。

对于每组测试数据，输入第一行包含一个正整数 $n$ 表示节点数量

接下来 $n-1$ 行每行包含两个整数 $x1,y1$，表示树 $S$ 上的一条边，连接 $x1,y1$ 两个节点，这条边的边权为 $1$

接下来 $n-1$ 行每行包含两个整数 $x2,y2$，表示树 $T$ 上的一条边，连接 $x2,y2$ 两个节点，这条边的边权为 $0$

输出格式

对于每组测试数据输出一行，如果 $S$ 可以通过消除操作变成 $T$，则输出 Ok 否则输出 No

数据范围

对于 $40\%$ 的数据满足：$2 \leq n \leq 200$

对于 $60\%$ 的数据满足：$2 \leq n \leq 2000$

对于 $100\%$ 的数据满足：$1 \leq T \leq 10,2 \leq n \leq 50000, 1 \leq x1,x2,y1,y2 \leq n, x1 \ne y1, x2 \ne y2$

特别的，保证输入数据为树

样例输入

1
3
1 2
2 3
1 3
3 2

样例输出

Ok

样例解释

先对 $1-2-3$ 进行一次消除，删除 $1-2$，增加 $1-3$

再对 $2-3$ 进行一次消除，删除 $2-3$，增加 $2-3$

得到树 $T$