Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Tajian løser følgende oppgave:

Gitt en graf med $n$ punkter, har den opprinnelige grafen ingen kanter. Tajian har noen kanter som kan legges til i grafen, og han har delt disse kantene inn i $k$ grupper, der den $i$-te gruppen inneholder $c_i$ kanter. For hver $x \in [1, n]$ ønsker Tajian å vite det minimale antallet kantgrupper han må velge fra disse $k$ gruppene for å legge til i grafen, slik at han er sikker på at antallet sammenhengende komponenter i grafen ikke overstiger $x$.

Selv om det ikke er umiddelbart åpenbart, finnes det artikler som viser at det minimale fargeleggingstallet til et utspennende tre er et NPC-problem. Tajian vet imidlertid ikke dette, så han vil at du skal hjelpe ham med å løse denne oppgaven.

Inndata

Et enkelt testtilfelle inneholder flere datasett.

Den første linjen i inndataene er antall datasett $T$ ($1 \le T \le 10^3$), som representerer antall datasett i dette testtilfellet.

For hvert datasett inneholder den første linjen to heltall $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), som representerer antall punkter og antall kantgrupper.

Den neste delen beskriver informasjonen for de $k$ kantgruppene. For den $i$-te kantgruppen inneholder den første linjen et heltall $c_i$ ($1 \le c_i \le 200$), som representerer antall kanter i denne gruppen. De påfølgende $c_i$ linjene inneholder hver to heltall $u, v$ ($1 \le u, v \le n, u \neq v$), som representerer en kant i denne gruppen.

For et enkelt datasett er det garantert at $\sum c_i \le 200$. For alle data samlet er det garantert at $\sum 2^n \le 2^{16}$.

Utdata

For hvert datasett skal du skrive ut en linje med $n$ heltall, der det $i$-te heltallet representerer svaret når $x = i$.

Hvis det under enhver omstendighet er umulig å sikre at antallet sammenhengende komponenter ikke overstiger $i$, skriv ut "-1".

Eksempler

Inndata 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

Utdata 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.