Piggy (quien, en su tiempo libre, administra la Comisión de Protocolo de Conectividad Interestelar) se enfrenta a un delicado dilema de hardware. La red de comunicación más reciente, que consta de $n$ estaciones de relevo conectadas por $(n - 1)$ enlaces de fibra óptica para formar una estructura de árbol, finalmente está lista para su despliegue. Sin embargo, el sistema debe encenderse con extrema precaución.

El proceso de activación implica disparar pulsos láser a lo largo de rutas específicas. Una ruta se define como la ruta simple única entre dos estaciones. Debido al riesgo catastrófico de la "Interferencia de Retroflujo Cuántico" —un fenómeno que mantiene a los abogados de la comisión despiertos por la noche—, se debe observar estrictamente el siguiente protocolo:

• Las rutas de transmisión deben establecerse una por una.
• Para evitar sobrecargas de energía, cada ruta recién establecida puede compartir como máximo una estación con el conjunto de estaciones ya activadas por cualquier ruta anterior.

Formalmente, sea $S$ el conjunto de estaciones actualmente activadas. Para cualquier nueva ruta $P$ que consista en un conjunto de estaciones $V(P)$, debe cumplirse la condición $|V(P) \cap S| \le 1$. Una vez que una ruta se dispara con éxito, todas las estaciones a lo largo de esa ruta se consideran parte del conjunto activado $S$.

Su misión, si decide aceptarla, es determinar el número mínimo de pulsos láser necesarios para activar cada estación en toda la red y proporcionar una de dichas secuencias de rutas para satisfacer al departamento legal.

La ilustración de los dos primeros casos de prueba. Observe que en el Caso 2, el segundo pulso comparte solo la estación 2 con el primero, cumpliendo con la regla de no interferencia.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^4$) que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene un entero $n$ ($2 \le n \le 3 \times 10^5$), el número de estaciones en la red.

Para las siguientes $(n - 1)$ líneas, la $i$-ésima línea contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), que describen un enlace bidireccional de fibra óptica entre la estación $u_i$ y la estación $v_i$.

Se garantiza que los enlaces forman un árbol y que la suma de $n$ sobre todos los casos de prueba no excede $3 \times 10^5$.

Salida

Para cada caso de prueba, imprima el número mínimo de rutas $k$ en la primera línea. A continuación, imprima $k$ líneas, cada una conteniendo dos enteros $a_i$ y $b_i$, que representan los puntos finales de la $i$-ésima ruta en la secuencia. Tenga en cuenta que $a_i$ puede ser igual a $b_i$ si la ruta consiste en una sola estación.

Si existen múltiples secuencias óptimas, se aceptará cualquiera que siga estrictamente el protocolo de no interferencia.

Ejemplos

Entrada 1

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

Salida 1

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