Universal Cup Judging System

Universal Cup

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

Тадзянь (Tajian) решает следующую задачу:

Дан граф с $n$ вершинами, изначально в графе нет рёбер. У Тадзяня есть несколько рёбер для добавления в граф, и он разделил эти рёбра на $k$ групп, где $i$-я группа содержит $c_i$ рёбер. Для каждого $x \in [1, n]$ Тадзянь хочет узнать минимальное количество групп рёбер, которые ему нужно выбрать из этих $k$ групп и добавить в граф, чтобы гарантировать, что количество компонент связности в графе не превысит $x$.

Хотя это не сразу очевидно, существуют статьи, указывающие на то, что минимальное число цветов остовного дерева является NPC-задачей. Однако Тадзянь этого не знает, поэтому просит вас помочь ему решить эту задачу.

Входные данные

Один тест содержит несколько наборов данных.

Первая строка входных данных содержит число наборов данных $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.