Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Tajian đang giải quyết bài toán sau:

Cho một đồ thị gồm $n$ điểm, đồ thị ban đầu không có cạnh nào. Tajian có một số cạnh cần thêm vào đồ thị, và anh ấy đã chia các cạnh này thành $k$ nhóm, trong đó nhóm thứ $i$ chứa $c_i$ cạnh. Với mỗi $x \in [1, n]$, Tajian muốn biết số lượng nhóm cạnh tối thiểu mà anh ấy cần chọn từ $k$ nhóm này để thêm vào đồ thị nhằm đảm bảo số thành phần liên thông trong đồ thị không vượt quá $x$.

Mặc dù điều này không hiển nhiên ngay lập tức, có những bài báo khoa học chỉ ra rằng sắc số tối thiểu của cây khung là một bài toán NPC. Tuy nhiên, Tajian không biết điều này, vì vậy anh ấy muốn bạn giúp anh ấy giải bài toán này.

Dữ liệu vào

Một test đơn lẻ chứa nhiều bộ dữ liệu.

Dòng đầu tiên của dữ liệu vào là số lượng bộ dữ liệu $T$ ($1 \le T \le 10^3$), biểu thị số bộ dữ liệu trong test này.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), biểu thị số lượng điểm và số lượng nhóm cạnh.

Phần tiếp theo mô tả thông tin cho $k$ nhóm cạnh. Đối với nhóm cạnh thứ $i$, dòng đầu tiên chứa một số nguyên $c_i$ ($1 \le c_i \le 200$), biểu thị số lượng cạnh trong nhóm này. $c_i$ dòng tiếp theo mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n, u \neq v$), biểu thị một cạnh trong nhóm này.

Đối với một bộ dữ liệu đơn lẻ, đảm bảo rằng $\sum c_i \le 200$. Đối với tất cả dữ liệu, đảm bảo rằng $\sum 2^n \le 2^{16}$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng gồm $n$ số nguyên, trong đó số nguyên thứ $i$ biểu thị đáp án khi $x = i$.

Nếu không thể đảm bảo rằng số lượng thành phần liên thông không vượt quá $i$ trong bất kỳ trường hợp nào, hãy in ra "-1".

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 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.