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