Universal Cup Judging System

Universal Cup

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

Tajian は次の問題を解いています:

$n$ 個の頂点を持つグラフが与えられ、初期状態では辺がありません。Tajian はグラフに追加するためのいくつかの辺を持っており、これらの辺を $k$ 個のグループに分けました。ここで、$i$ 番目のグループには $c_i$ 本の辺が含まれています。各 $x \in [1, n]$ について、Tajian はグラフの連結成分の個数が $x$ 以下になることを保証するために、これら $k$ 個のグループから選んでグラフに追加する必要がある辺のグループの最小個数を知りたいと考えています。

一見すると明らかではありませんが、全域木の最小彩色数が NPC 問題であることを示す論文が存在します。しかし、Tajian はそのことを知らないため、あなたにこの問題を解くのを手伝ってほしいと思っています。

入力

$1$ つのテストケースには複数のデータセットが含まれます。

入力の最初の行はデータセット数 $T$ ($1 \le T \le 10^3$) であり、このテストケースに含まれるデータセットの個数を表します。

各データセットについて、最初の行には頂点の個数と辺のグループの個数を表す $2$ つの整数 $n, k$ ($2 \le n \le 16, 1 \le k \le 200$) が含まれます。

続く部分では、$k$ 個の辺のグループの情報が記述されます。$i$ 番目の辺のグループについて、最初の行にはこのグループに含まれる辺の本数を表す整数 $c_i$ ($1 \le c_i \le 200$) が含まれます。続く $c_i$ 行にはそれぞれ、このグループに含まれる辺を表す $2$ つの整数 $u, v$ ($1 \le u, v \le n, u \neq v$) が含まれます。

単一のデータセットについて、$\sum c_i \le 200$ が保証されます。すべてのデータについて、$\sum 2^n \le 2^{16}$ が保証されます。

出力

各データセットについて、$n$ 個の整数を $1$ 行に出力してください。ここで、$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.