Universal Cup Judging System

Universal Cup

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

Tajian 正在解決以下問題:

給定一個含有 $n$ 個點嘅圖,初始時圖入面冇邊。Tajian 有一啲邊需要加落個圖度,佢將呢啲邊分成咗 $k$ 組,其中第 $i$ 組包含 $c_i$ 條邊。對於每個 $x \in [1, n]$,Tajian 想知道,佢最少需要從呢 $k$ 組邊入面揀幾多組邊加落個圖度,先至可以確保圖入面嘅連通分量個數唔超過 $x$。

雖然呢樣嘢唔係一眼就睇得出,但係有論文指出,生成樹嘅最小著色數係一個 NPC 問題。然而,Tajian 並唔知道呢一點,所以佢希望你幫佢解決呢個問題。

輸入格式

單個測試點包含多組測試數據。

輸入嘅第一行係測試數據組數 $T$($1 \le T \le 10^3$),表示呢個測試點入面嘅測試數據組數。

對於每組測試數據,第一行包含兩個整數 $n, k$($2 \le n \le 16, 1 \le k \le 200$),分別表示點嘅數量同埋邊組嘅數量。

跟住落嚟嘅部分描述呢 $k$ 組邊嘅資訊。對於第 $i$ 組邊,第一行包含一個整數 $c_i$($1 \le c_i \le 200$),表示呢組入面嘅邊數。跟住落嚟嘅 $c_i$ 行,每行包含兩個整數 $u, v$($1 \le u, v \le n, u \neq v$),表示呢組入面嘅一條邊。

對於單組測試數據,保證 $\sum c_i \le 200$。對於所有數據,保證 $\sum 2^n \le 2^{16}$。

輸出格式

對於每組測試數據,輸出一行 $n$ 個整數,其中第 $i$ 個整數表示當 $x = i$ 時嘅答案。

如果喺任何情況下都無法確保連通分量個數唔超過 $i$,就輸出 "-1"。

範例

輸入格式 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

輸出格式 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.