Se te da un árbol no dirigido con $n$ vértices. Una hoja es un vértice de grado $1$. Sea $k$ el número de hojas; inicialmente, hay una ficha en cada hoja, por lo que hay $k$ fichas en total.

Para cada ficha, debes elegir una secuencia infinita de hojas $a_1, a_2, a_3, \ldots$ con $a_i \ne a_{i+1}$ para todo $i \ge 1$, y con $a_1 \ne v$, donde $v$ es la hoja en la que comienza la ficha. Las secuencias de las distintas fichas se pueden elegir de forma independiente. La secuencia elegida determina la ruta de la ficha: primero recorre el camino más corto de $v$ a $a_1$, después el camino más corto de $a_1$ a $a_2$, luego de $a_2$ a $a_3$, y así sucesivamente, indefinidamente.

En un movimiento, cada ficha recorre simultáneamente exactamente una arista de su propia ruta. Ninguna ficha puede quedarse en el mismo lugar.

Determina si se pueden elegir las secuencias de modo que, tras un número finito de movimientos, las $k$ fichas estén en la misma hoja al mismo tiempo.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 10^4$): el número de casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($2 \le n \le 2 \cdot 10^5$): el número de vértices del árbol.

Cada una de las siguientes $n-1$ líneas contiene dos enteros $u$ y $v$ ($1 \le u, v \le n$): una arista bidireccional entre los vértices $u$ y $v$. Se garantiza que estas aristas forman un árbol.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $2 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime la respuesta en una línea separada. Si es posible elegir las secuencias requeridas para todas las fichas de modo que todas se reúnan en una hoja al mismo tiempo, imprime YES; en caso contrario, imprime NO.

Ejemplos

Entrada 1

5
2
1 2
3
2 1
2 3
4
1 2
1 3
3 4
6
1 2
2 3
2 4
4 5
4 6
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8

Salida 1

NO
NO
NO
NO
YES