Universal Cup Judging System

Universal Cup

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

Tajian sedang menyelesaikan persoalan berikut:

Diberikan sebuah graf dengan $n$ titik, graf awal tidak memiliki sisi. Tajian memiliki beberapa sisi untuk ditambahkan ke dalam graf, dan ia telah membagi sisi-sisi ini ke dalam $k$ kelompok, di mana kelompok ke-$i$ berisi $c_i$ sisi. Untuk setiap $x \in [1, n]$, Tajian ingin mengetahui jumlah kelompok sisi minimum yang perlu ia pilih dari $k$ kelompok tersebut untuk ditambahkan ke dalam graf guna memastikan bahwa banyaknya komponen terhubung di dalam graf tidak melebihi $x$.

Meskipun tidak langsung terlihat jelas, terdapat makalah yang menunjukkan bahwa bilangan pewarnaan minimum dari pohon merentang (spanning tree) adalah persoalan NPC. Namun, Tajian tidak mengetahui hal ini, sehingga ia ingin Anda membantunya menyelesaikan persoalan ini.

Masukan

Satu kasus uji berisi beberapa set data (data set).

Baris pertama masukan adalah banyaknya set data $T$ ($1 \le T \le 10^3$), yang menyatakan banyaknya set data dalam kasus uji ini.

Untuk setiap set data, baris pertama berisi dua bilangan bulat $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), yang menyatakan banyaknya titik dan banyaknya kelompok sisi.

Bagian berikutnya mendeskripsikan informasi untuk $k$ kelompok sisi. Untuk kelompok sisi ke-$i$, baris pertama berisi sebuah bilangan bulat $c_i$ ($1 \le c_i \le 200$), yang menyatakan banyaknya sisi dalam kelompok ini. $c_i$ baris berikutnya masing-masing berisi dua bilangan bulat $u, v$ ($1 \le u, v \le n, u \neq v$), yang menyatakan sebuah sisi dalam kelompok ini.

Untuk satu set data, dijamin bahwa $\sum c_i \le 200$. Untuk seluruh data, dijamin bahwa $\sum 2^n \le 2^{16}$.

Keluaran

Untuk setiap set data, keluarkan satu baris berisi $n$ bilangan bulat, di mana bilangan bulat ke-$i$ menyatakan jawaban ketika $x = i$.

Jika tidak mungkin memastikan bahwa banyaknya komponen terhubung tidak melebihi $i$ dalam keadaan apa pun, keluarkan "-1".

Contoh

Masukan 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

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