Universal Cup Judging System

Universal Cup

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

Tajian er að leysa eftirfarandi verkefni:

Gefið er net með $n$ punktum, upphaflega netið hefur enga leggi. Tajian er með nokkra leggi til að bæta við netið og hann hefur skipt þessum leggjum í $k$ hópa, þar sem $i$-ti hópurinn inniheldur $c_i$ leggi. Fyrir hvert $x \in [1, n]$ vill Tajian vita lágmarksfjölda hópa af leggjum sem hann þarf að velja úr þessum $k$ hópum til að bæta við netið svo tryggt sé að fjöldi samanhangandi þátta í netinu fari ekki yfir $x$.

Þótt það sé ekki augljóst við fyrstu sýn eru til greinar sem benda á að lágmarkslitunartala spannandi trés sé NPC-verkefni. Hins vegar veit Tajian þetta ekki, svo hann vill að þú hjálpir sér að leysa þetta verkefni.

Inntak

Eitt prófunartilvik inniheldur mörg gagnasett.

Fyrsta línan í inntakinu er fjöldi gagnasetta $T$ ($1 \le T \le 10^3$), sem táknar fjölda gagnasetta í þessu prófunartilviki.

Fyrir hvert gagnasett inniheldur fyrsta línan tvær heiltölur $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), sem tákna fjölda punkta og fjölda hópa af leggjum.

Næsti hluti lýsir upplýsingunum fyrir $k$ hópa leggja. Fyrir $i$-ta hóp leggja inniheldur fyrsta línan heiltölu $c_i$ ($1 \le c_i \le 200$), sem táknar fjölda leggja í þessum hópi. Næstu $c_i$ línur innihalda hver um sig tvær heiltölur $u, v$ ($1 \le u, v \le n, u \neq v$), sem tákna legg í þessum hópi.

Fyrir eitt gagnasett er tryggt að $\sum c_i \le 200$. Fyrir öll gögn er tryggt að $\sum 2^n \le 2^{16}$.

Úttak

Fyrir hvert gagnasett skal prenta línu með $n$ heiltölum, þar sem $i$-ta heiltalan táknar svarið þegar $x = i$.

Ef ómögulegt er að tryggja að fjöldi samanhangandi þátta fari ekki yfir $i$ undir nokkrum kringumstæðum skal prenta "-1".

Dæmi

Inntak 1

4
3 3
1
1 2
1
2 3
1
1 3
4 3
1
2 3
2
1 2
1 3
1
3 4
6 2
3
1 2
3 4
5 6
2
2 3
4 5
4 2
1
2 3
2
1 3
1 2

Úttak 1

2 1 0
2 1 1 0
2 2 1 1 1 0
-1 1 1 0

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.