Заглянем во вселенную, в которой каждый житель — это некоторое дерево, описываемое количеством вершин $$$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