Tajian rozwiązuje następujące zadanie:
Dany jest graf o $n$ punktach, który początkowo nie ma żadnych krawędzi. Tajian ma pewne krawędzie do dodania do grafu i podzielił je na $k$ grup, gdzie $i$-ta grupa zawiera $c_i$ krawędzi. Dla każdego $x \in [1, n]$ Tajian chce wiedzieć, ile minimalnie grup krawędzi musi wybrać spośród tych $k$ grup i dodać do grafu, aby zagwarantować, że liczba spójnych składowych w grafie nie przekroczy $x$.
Choć nie jest to od razu oczywiste, istnieją prace naukowe wskazujące, że minimalna liczba kolorów drzewa rozpinającego jest problemem NPC. Tajian jednak o tym nie wie, dlatego chce, abyś pomógł mu rozwiązać to zadanie.
Wejście
Pojedynczy przypadek testowy zawiera wiele zestawów danych.
Pierwszy wiersz wejścia zawiera liczbę zestawów danych $T$ ($1 \le T \le 10^3$), oznaczającą liczbę zestawów danych w tym przypadku testowym.
Dla każdego zestawu danych pierwszy wiersz zawiera dwie liczby całkowite $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), oznaczające liczbę punktów oraz liczbę grup krawędzi.
Kolejna część opisuje informacje o $k$ grupach krawędzi. Dla $i$-tej grupy krawędzi pierwszy wiersz zawiera liczbę całkowitą $c_i$ ($1 \le c_i \le 200$), oznaczającą liczbę krawędzi w tej grupie. Kolejne $c_i$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u, v \le n, u \neq v$), oznaczające krawędź w tej grupie.
Dla pojedynczego zestawu danych gwarantowane jest, że $\sum c_i \le 200$. Dla wszystkich danych gwarantowane jest, że $\sum 2^n \le 2^{16}$.
Wyjście
Dla każdego zestawu danych wypisz wiersz zawierający $n$ liczb całkowitych, gdzie $i$-ta liczba całkowita oznacza odpowiedź dla $x = i$.
Jeśli w żadnych okolicznościach nie da się zapewnić, by liczba spójnych składowych nie przekroczyła $i$, wypisz "-1".
Przykład
Wejście 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
Wyjście 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0