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öst das folgende Problem:

Gegeben ist ein Graph mit $n$ Punkten; der ursprüngliche Graph hat keine Kanten. Tajian hat einige Kanten, die er zum Graphen hinzufügen möchte, und er hat diese Kanten in $k$ Gruppen unterteilt, wobei die $i$-te Gruppe $c_i$ Kanten enthält. Für jedes $x \in [1, n]$ möchte Tajian wissen, wie viele Kantengruppen er mindestens aus diesen $k$ Gruppen auswählen und zum Graphen hinzufügen muss, um sicherzustellen, dass die Anzahl der Zusammenhangskomponenten im Graphen $x$ nicht überschreitet.

Obwohl es nicht sofort offensichtlich ist, gibt es wissenschaftliche Arbeiten, die zeigen, dass die minimale Färbungszahl eines Spannbaums ein NPC-Problem ist. Tajian weiß dies jedoch nicht und möchte daher, dass du ihm bei der Lösung dieses Problems hilfst.

Eingabe

Ein einzelner Testfall enthält mehrere Datensätze.

Die erste Zeile der Eingabe ist die Anzahl der Datensätze $T$ ($1 \le T \le 10^3$), die die Anzahl der Datensätze in diesem Testfall angibt.

Für jeden Datensatz enthält die erste Zeile zwei ganze Zahlen $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), die die Anzahl der Punkte und die Anzahl der Kantengruppen angeben.

Der nächste Abschnitt beschreibt die Informationen für die $k$ Kantengruppen. Für die $i$-te Kantengruppe enthält die erste Zeile eine ganze Zahl $c_i$ ($1 \le c_i \le 200$), die die Anzahl der Kanten in dieser Gruppe angibt. Die folgenden $c_i$ Zeilen enthalten jeweils zwei ganze Zahlen $u, v$ ($1 \le u, v \le n, u \neq v$), die eine Kante in dieser Gruppe darstellen.

Für einen einzelnen Datensatz wird garantiert, dass $\sum c_i \le 200$ gilt. Für alle Daten zusammen wird garantiert, dass $\sum 2^n \le 2^{16}$ gilt.

Ausgabe

Gib für jeden Datensatz eine Zeile mit $n$ ganzen Zahlen aus, wobei die $i$-te ganze Zahl die Antwort für $x = i$ darstellt.

Falls es unter keinen Umständen möglich ist sicherzustellen, dass die Anzahl der Zusammenhangskomponenten $i$ nicht überschreitet, gib "-1" aus.

Beispiele

Eingabe 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

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