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 (der in seiner Freizeit die Kommission für Interstellare Konnektivitätsprotokolle leitet) steht vor einem heiklen Hardware-Rätsel. Das neueste Kommunikationsnetz, bestehend aus $n$ Relaisstationen, die durch $(n - 1)$ Glasfaserverbindungen zu einer Baumstruktur verbunden sind, ist endlich einsatzbereit. Allerdings muss das System mit äußerster Vorsicht eingeschaltet werden.

Der Aktivierungsprozess beinhaltet das Abfeuern von Laserimpulsen entlang bestimmter Pfade. Ein Pfad ist definiert als die eindeutige einfache Verbindung zwischen zwei Stationen. Wegen des katastrophalen Risikos einer „Quanten-Rückfluss-Interferenz“ — eines Phänomens, das den Anwälten der Kommission schlaflose Nächte bereitet — muss das folgende Protokoll strikt eingehalten werden:

  • Übertragungspfade müssen nacheinander einzeln eingerichtet werden.
  • Um Spannungsspitzen zu vermeiden, darf jeder neu eingerichtete Pfad höchstens eine Station mit der Menge der Stationen gemeinsam haben, die bereits durch einen vorherigen Pfad aktiviert wurden.

Formal sei $S$ die Menge der aktuell aktivierten Stationen. Für jeden neuen Pfad $P$, der aus einer Menge von Stationen $V(P)$ besteht, muss die Bedingung $|V(P) \cap S| \le 1$ gelten. Sobald ein Pfad erfolgreich abgefeuert wurde, gelten alle Stationen entlang dieses Pfades als Teil der aktivierten Menge $S$.

Ihre Mission, sollten Sie diese annehmen, besteht darin, die minimale Anzahl von Laserimpulsen zu bestimmen, die erforderlich ist, um jede Station im gesamten Netzwerk zu aktivieren, und eine solche Folge von Pfaden anzugeben, um die Rechtsabteilung zufriedenzustellen.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Die Darstellung der ersten beiden Beispieltestfälle. Beachten Sie, dass in Fall 2 der zweite Impuls nur Station $2$ mit dem ersten teilt und somit die Nicht-Interferenz-Regel erfüllt.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält eine ganze Zahl $n$ ($2 \le n \le 3 \times 10^5$), die Anzahl der Stationen im Netz.

In den folgenden $(n - 1)$ Zeilen enthält die $i$-te Zeile zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), die eine bidirektionale Glasfaserverbindung zwischen Station $u_i$ und Station $v_i$ beschreiben.

Es wird garantiert, dass die Verbindungen einen Baum bilden und dass die Summe von $n$ über alle Testfälle $3 \times 10^5$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall in der ersten Zeile die minimale Anzahl von Pfaden $k$ aus. Geben Sie anschließend $k$ Zeilen aus, die jeweils zwei ganze Zahlen $a_i$ und $b_i$ enthalten, welche die Endpunkte des $i$-ten Pfades in der Folge darstellen. Beachten Sie, dass $a_i$ gleich $b_i$ sein kann, wenn der Pfad aus einer einzigen Station besteht.

Falls mehrere optimale Folgen existieren, wird jede akzeptiert, die das Nicht-Interferenz-Protokoll strikt einhält.

Beispiel

Eingabe

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

Ausgabe

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.