Universal Cup Judging System

Universal Cup

実行時間制限: 3.0 s メモリ制限: 2048 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

Piggy (som på sin fritid leder Kommissionen för Interstellära Konnektivitetsprotokoll) står inför ett känsligt hårdvarudilemma. Det senaste kommunikationsnätet, som består av $n$ relästationer sammanbundna av $(n - 1)$ fiberoptiska länkar i en trädstruktur, är äntligen redo att tas i bruk. Systemet måste dock slås på med största försiktighet.

Aktiveringsprocessen går ut på att avfyra laserpulser längs specifika vägar. En väg definieras som den unika enkla rutten mellan två stationer. På grund av den katastrofala risken för "Kvantbakflödesinterferens" — ett fenomen som håller kommissionens jurister vakna om nätterna — måste följande protokoll följas strikt:

  • Transmissionsvägar måste upprättas en i taget.
  • För att förhindra strömspikar får varje nyupprättad väg dela högst en station med mängden av stationer som redan aktiverats av någon tidigare väg.

Formellt, låt $S$ vara mängden av för närvarande aktiverade stationer. För varje ny väg $P$ bestående av en mängd stationer $V(P)$ måste villkoret $|V(P) \cap S| \le 1$ gälla. När en väg väl har avfyrats framgångsrikt räknas alla stationer längs den vägen som en del av den aktiverade mängden $S$.

Ditt uppdrag, om du väljer att acceptera det, är att bestämma det minsta antalet laserpulser som krävs för att aktivera varje station i hela nätverket och ange en sådan följd av vägar för att tillfredsställa juristavdelningen.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Illustration av de två första exempeltestfallen. Notera att i Fall 2 delar den andra pulsen endast station $2$ med den första, vilket uppfyller regeln om icke-interferens.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^4$) som anger antalet testfall. För varje testfall:

Den första raden innehåller ett heltal $n$ ($2 \le n \le 3 \times 10^5$), antalet stationer i nätet.

På de följande $(n - 1)$ raderna innehåller den $i$-te raden två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), som beskriver en dubbelriktad fiberoptisk länk mellan station $u_i$ och station $v_i$.

Det garanteras att länkarna bildar ett träd och att summan av $n$ över alla testfall inte överstiger $3 \times 10^5$.

Utdata

För varje testfall, skriv ut det minsta antalet vägar $k$ på den första raden. Därefter, skriv ut $k$ rader som var och en innehåller två heltal $a_i$ och $b_i$, vilka representerar ändpunkterna för den $i$-te vägen i följden. Notera att $a_i$ kan vara lika med $b_i$ om vägen består av en enda station.

Om det finns flera optimala följder accepteras vilken som helst som strikt följer icke-interferensprotokollet.

Exempel

Indata

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

Utdata

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.