Tajian은 다음 문제를 풀고 있습니다:
$n$개의 정점이 있는 그래프가 주어지며, 초기 그래프에는 간선이 없습니다. Tajian은 그래프에 추가할 몇 개의 간선을 가지고 있으며, 이 간선들을 $k$개의 그룹으로 나누었고 $i$번째 그룹에는 $c_i$개의 간선이 포함되어 있습니다. 각 $x \in [1, n]$에 대하여, Tajian은 그래프의 연결 요소의 개수가 $x$를 초과하지 않도록 보장하기 위해 이 $k$개의 그룹 중에서 선택하여 그래프에 추가해야 하는 간선 그룹의 최소 개수를 알고 싶어 합니다.
즉시 자명하지는 않지만, 스패닝 트리의 최소 채색수가 NPC 문제임을 나타내는 논문들이 있습니다. 하지만 Tajian은 이를 모르기 때문에, 당신이 이 문제를 해결하도록 도와주기를 원합니다.
입력
단일 테스트 케이스는 여러 데이터 세트를 포함합니다.
입력의 첫 번째 줄은 이 테스트 케이스의 데이터 세트 수를 나타내는 $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