Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 2048 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

Piggy (joka vapaa-ajallaan johtaa Tähtienvälisen Yhteyskäytäntökomission toimintaa) on hankalan laitteisto-ongelman edessä. Uusin viestintäverkko, joka koostuu $n$ linkkiasemasta ja niitä puurakenteeksi yhdistävästä $(n - 1)$ valokuituyhteydestä, on vihdoin valmis käyttöönottoon. Järjestelmä on kuitenkin käynnistettävä äärimmäisen varovasti.

Aktivointiprosessissa ammutaan laserpulsseja tiettyjä polkuja pitkin. Polku määritellään kahden aseman väliseksi yksikäsitteiseksi yksinkertaiseksi reitiksi. ”Kvanttitakaisinvirtausinterferenssin” – ilmiön, joka pitää komission lakimiehetvalveilla öisin – aiheuttaman katastrofaalisen riskin vuoksi seuraavaa protokollaa on noudatettava tiukasti:

  • Siirtopolut on muodostettava yksi kerrallaan.
  • Virtapiikkien estämiseksi jokainen uutena muodostettava polku saa sisältää enintään yhden yhteisen aseman aiempien polkujen jo aktivoimien asemien joukon kanssa.

Muodollisesti olkoon $S$ tällä hetkellä aktivoitujen asemien joukko. Jokaiselle uudelle polulle $P$, joka koostuu asemajoukosta $V(P)$, on pädettävä ehdon $|V(P) \cap S| \le 1$. Kun polku on onnistuneesti aktivoitu pulssilla, kaikki kyseisen polun varrella olevat asemat katsotaan osaksi aktivoitua joukkoa $S$.

Tehtäväsi, jos päätät ottaa sen vastaan, on määrittää pienin mahdollinen laserpulssien määrä, joka tarvitaan koko verkon jokaisen aseman aktivoimiseen, ja esittää yksi tällainen polkujen jono lakiosaston tyydyttämiseksi.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Kahden ensimmäisen esimerkkitestitapauksen havainnollistus. Huomaa, että tapauksessa 2 toinen pulssi jakaa ensimmäisen kanssa vain aseman $2$, mikä täyttää häiriöttömyyssäännön.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän. Jokaisessa testitapauksessa:

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 3 \times 10^5$), verkossa olevien asemien lukumäärän.

Seuraavilla $(n - 1)$ rivillä $i$-s rivi sisältää kaksi kokonaislukua $u_i$ ja $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), jotka kuvaavat kaksisuuntaista valokuituyhteyttä aseman $u_i$ ja aseman $v_i$ välillä.

On taattu, että yhteydet muodostavat puun ja että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $3 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden ensimmäiselle riville pienin polkujen lukumäärä $k$. Tulosta tämän jälkeen $k$ riviä, joista jokainen sisältää kaksi kokonaislukua $a_i$ ja $b_i$, jotka esittävät jonon $i$-nnen polun päätepisteitä. Huomaa, että $a_i$ voi olla yhtä suuri kuin $b_i$, jos polku koostuu yhdestä ainoasta asemasta.

Jos optimaalisia jonoja on useita, mikä tahansa häiriöttömyysprotokollaa tiukasti noudattava jono hyväksytään.

Esimerkki

Syöte

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

Tuloste

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.