Тадзянь (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