Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 2048 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Piggy (quien, en su tiempo libre, dirige la Comisión del 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 repetidoras 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 caminos específicos. Un camino se define como la única ruta simple entre dos estaciones. Debido al riesgo catastrófico de «Interferencia de Retroceso Cuántico» — un fenómeno que quita el sueño a los abogados de la comisión — se debe observar estrictamente el siguiente protocolo:

  • Los caminos de transmisión deben establecerse uno por uno.
  • Para evitar sobrecargas de energía, cada camino recién establecido puede compartir como máximo una estación con el conjunto de estaciones ya activadas por cualquier camino anterior.

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

Tu misión, si decides 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 secuencia de tales caminos para satisfacer al departamento legal.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Ilustración de los dos primeros casos de prueba de ejemplo. Observa que en el Caso 2, el segundo pulso comparte únicamente la estación $2$ con el primero, cumpliendo 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.

En 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$ en todos los casos de prueba no supera $3 \times 10^5$.

Salida

Para cada caso de prueba, imprime el número mínimo de caminos $k$ en la primera línea. A continuación, imprime $k$ líneas, cada una con dos enteros $a_i$ y $b_i$, que representan los extremos del $i$-ésimo camino en la secuencia. Ten en cuenta que $a_i$ puede ser igual a $b_i$ si el camino consta de una sola estación.

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

Ejemplo

Entrada

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 3
2
4 5
1 3
3
7 7
1 6
4 5

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.