Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Tajian rozwiązuje następujące zadanie:

Dany jest graf o $n$ punktach, który początkowo nie ma żadnych krawędzi. Tajian ma pewne krawędzie do dodania do grafu i podzielił je na $k$ grup, gdzie $i$-ta grupa zawiera $c_i$ krawędzi. Dla każdego $x \in [1, n]$ Tajian chce wiedzieć, ile minimalnie grup krawędzi musi wybrać spośród tych $k$ grup i dodać do grafu, aby zagwarantować, że liczba spójnych składowych w grafie nie przekroczy $x$.

Choć nie jest to od razu oczywiste, istnieją prace naukowe wskazujące, że minimalna liczba kolorów drzewa rozpinającego jest problemem NPC. Tajian jednak o tym nie wie, dlatego chce, abyś pomógł mu rozwiązać to zadanie.

Wejście

Pojedynczy przypadek testowy zawiera wiele zestawów danych.

Pierwszy wiersz wejścia zawiera liczbę zestawów danych $T$ ($1 \le T \le 10^3$), oznaczającą liczbę zestawów danych w tym przypadku testowym.

Dla każdego zestawu danych pierwszy wiersz zawiera dwie liczby całkowite $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), oznaczające liczbę punktów oraz liczbę grup krawędzi.

Kolejna część opisuje informacje o $k$ grupach krawędzi. Dla $i$-tej grupy krawędzi pierwszy wiersz zawiera liczbę całkowitą $c_i$ ($1 \le c_i \le 200$), oznaczającą liczbę krawędzi w tej grupie. Kolejne $c_i$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u, v \le n, u \neq v$), oznaczające krawędź w tej grupie.

Dla pojedynczego zestawu danych gwarantowane jest, że $\sum c_i \le 200$. Dla wszystkich danych gwarantowane jest, że $\sum 2^n \le 2^{16}$.

Wyjście

Dla każdego zestawu danych wypisz wiersz zawierający $n$ liczb całkowitych, gdzie $i$-ta liczba całkowita oznacza odpowiedź dla $x = i$.

Jeśli w żadnych okolicznościach nie da się zapewnić, by liczba spójnych składowych nie przekroczyła $i$, wypisz "-1".

Przykład

Wejście 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

Wyjście 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.