Деревянный Морти
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заглянем во вселенную, в которой каждый житель — это некоторое дерево, описываемое количеством вершин $$$n$$$ и $$$n - 1$$$ ребрами между ними.

Неизвестно, зачем, но Рик уже третий день сидит и анализирует родственные связи между жителями этого измерения. Возможно, он подозревает, что Морти этого измерения подменили? Кто знает.

Рик считает, что дерево $$$T_1$$$ может быть потомком дерева $$$T_2$$$, если можно добавить к $$$T_2$$$ некоторое количество (возможно ноль) вершин и ребер, и перенумеровать его вершины так, чтобы оно стало совпадать с $$$T_1$$$.

Всего Рика интересует $$$t$$$ пар жителей этого измерения. Для каждой данной пары деревьев проверьте, может ли первое дерево быть потомком второго дерева.

Входные данные

Первая строка содержит целое число $$$t$$$ — количество интересующих Рика пар деревьев ($$$1 \le t \le 10^4$$$). После этого следуют $$$t$$$ описаний пар деревьев.

Первая строка каждого описания содержит целое число $$$n$$$ — размер дерева ($$$2 \le n \le 10^5$$$). Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ — концы $$$i$$$-го ребра первого дерева ($$$1 \le u_i, v_i \le n$$$). В следующих двух строках в том же формате задано второе дерево на $$$m$$$ вершинах.

Гарантируется, что сумма $$$n$$$ по всем парам деревьев не превышает $$$5 \cdot 10^5$$$, и сумма $$$n \cdot m$$$ не превышает $$$10^7$$$.

Выходные данные

Для каждой из $$$t$$$ пар деревьев напечатайте «YES», если первое дерево может быть потомком второго дерева, и «NO» в противном случае.

Пример

Входные данные
2
5
1 2
1 5
2 3
2 4
4
1 2
1 3
1 4
6
1 2
1 3
1 4
5 1
6 1
4
1 2
2 3
3 4
Выходные данные
YES
NO