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은 그래프의 연결 요소의 개수가 $x$를 초과하지 않도록 보장하기 위해 이 $k$개의 그룹 중에서 선택하여 그래프에 추가해야 하는 간선 그룹의 최소 개수를 알고 싶어 합니다.

즉시 자명하지는 않지만, 스패닝 트리의 최소 채색수가 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.