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