Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 2048 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

Piggy (sem í frítíma sínum stýrir Nefnd um samskiptastaðla milli stjarna) stendur frammi fyrir vandasamri vélbúnaðarþraut. Nýjasta fjarskiptanetið, sem samanstendur af $n$ endurvarpsstöðvum sem tengdar eru saman með $(n - 1)$ ljósleiðaratengingum í trjágrind, er loksins tilbúið til uppsetningar. Hins vegar verður að ræsa kerfið með ýtrustu aðgát.

Virkjunarferlið felst í því að skjóta leysipúlsum eftir ákveðnum vegum. Vegur er skilgreindur sem hinn ótvíræði einfaldi vegur milli tveggja stöðva. Vegna hættunnar á „skammtafræðilegri bakflæðistruflun“ — fyrirbæri sem heldur lögfræðingum nefndarinnar andvaka á nóttunni — verður að fylgja eftirfarandi reglum í hvívetna:

  • Koma verður á sendingarvegum einum í einu.
  • Til að koma í veg fyrir álagsbylgjur má hver nýr vegur deila í mesta lagi einni stöð með mengi þeirra stöðva sem þegar hafa verið virkjaðar af fyrri vegum.

Formlega, látum $S$ vera mengi þeirra stöðva sem nú eru virkar. Fyrir hvern nýjan veg $P$ sem samanstendur af mengi stöðva $V(P)$ verður skilyrðið $|V(P) \cap S| \le 1$ að gilda. Um leið og búið er að skjóta púlsi eftir vegi teljast allar stöðvar á þeim vegi hluti af virkjaða menginu $S$.

Verkefni þitt, ef þú kýst að taka því, er að ákvarða lágmarksfjölda leysipúlsa sem þarf til að virkja sérhverja stöð í öllu netinu og gefa upp eina slíka runu af vegum til að friða lögfræðideildina.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Skýringarmynd af fyrstu tveimur prófunartilvikunum í dæminu. Athugið að í Tilviki 2 deilir annar púlsinn aðeins stöð $2$ með þeim fyrsta, sem uppfyllir regluna um truflanaleysi.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^4$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur heiltölu $n$ ($2 \le n \le 3 \times 10^5$), fjölda stöðva í netinu.

Í næstu $(n - 1)$ línum inniheldur $i$-ta línan tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), sem lýsa tvístefnu ljósleiðaratengingu milli stöðvar $u_i$ og stöðvar $v_i$.

Tryggt er að tengingarnar myndi tré og að summa $n$ yfir öll prófunartilvik fari ekki yfir $3 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta lágmarksfjölda vega $k$ á fyrstu línuna. Þar á eftir skal prenta $k$ línur, þar sem hver lína inniheldur tvær heiltölur $a_i$ og $b_i$ sem tákna endapunkta $i$-ta vegarins í rununni. Athugið að $a_i$ má vera jafnt $b_i$ ef vegurinn samanstendur af einni stöð.

Ef fleiri en ein ákjósanleg runa er til verður hvaða runa sem er, sem fylgir reglunni um truflanaleysi í hvívetna, samþykkt.

Dæmi

Inntak

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

Úttak

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.