Read problems statements in [Hindi], [Spanish], [Mandarin chinese], [Russian], [Vietnamese] and [Bengali] as well.

Ada is one of the best hairdressers in ChefLand. She invented a very cool hair style and named it "power tree".

A power tree with degree $l$ — let's denote it by $PT(l)$ — is a directed graph, which can be constructed recursively as follows:
$PT(0)$ consists of a single node.
For $l > 0$:
- Create one node $u$ — the *root* of power tree $PT(l)$.
- Construct all power trees with smaller degrees, i.e. $PT(0), PT(1), \dots, PT(l-1)$.
- For each of the tree created in the previous step, add a directed edge from $u$ to its root.

Today, Ada is going to cut the hair of some customers. Of course, all of them want to have a power tree hair style!

A customer's uncut hair is represented by a directed graph with $N$ vertices (numbered $1$ through $N$) and exactly one edge between each pair of vertices. Ada should remove some edges (possibly none) from this graph in such a way that the resulting graph is a power tree. Note that she is not allowed to remove vertices!

Can you help Ada find the edges she should remove?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the next $N \choose 2$ lines contains two space-separated integers $u$ and $v$ describing a directed edge from vertex $u$ to vertex $v$. The edges are numbered $1$ through $N \choose 2$ in this order.

------  Output ------
For each test case:
If it is impossible to create a power tree, print a single line containing one integer $-1$.
Otherwise, print two lines. The first of these lines should contain a single integer $e$ denoting the number of edges to remove. The second line should contain $e$ space-separated integers denoting the numbers of the edges to remove.

If there are multiple answers, you may print any one.

------  Constraints  ------
$1 ≤ T ≤ 128$
$2 ≤ N ≤ 256$
$1 ≤ u, v ≤ N$
there is exactly one edge between each pair of vertices

----- Sample Input 1 ------ 
1

4

1 4

2 1

2 4

3 1

3 2

3 4
----- Sample Output 1 ------ 
3

1 3 4
----- explanation 1 ------ 
Example case 1: Ada should remove edges $(1, 4)$, $(2, 4)$ and $(3, 1)$. The resulting graph is a power tree with degree $l=2$.

Source: codechef | Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Constructive algorithms


Solutions:
pow_2 = [1, 2, 4, 8, 16, 32, 64, 128, 256]

def solve(N, G, L):
	if not N in pow_2:
		print(-1)
		return
	V = [i for i in range(0, N)]
	while len(V) > 1:
		i = 0
		C = []
		while i < len(V) - 1:
			u = V[i]
			v = V[i + 1]
			if G[u][v] != 0:
				C.append(u)
				L.remove((u, v))
			else:
				C.append(v)
				L.remove((v, u))
			i += 2
		V = C
	print(len(L))
	for i in range(0, len(L) - 1):
		print(G[L[i][0]][L[i][1]], end=' ')
	if len(L) != 0:
		print(G[L[-1][0]][L[-1][1]])
	else:
		print('')
T = int(input())
for i in range(0, T):
	N = int(input())
	G = [[0 for j in range(0, N)] for i in range(0, N)]
	L = []
	for i in range(0, N * (N - 1) // 2):
		(u, v) = [int(s) for s in input().split(' ') if s != '']
		G[u - 1][v - 1] = i + 1
		L.append((u - 1, v - 1))
	solve(N, G, L)


powers_of_two = [2 ** x for x in range(11)]

def power_root(l, r, adj_matrix, keep_edges):
	if l == r:
		return l
	mid = (l + r) // 2
	root1 = power_root(l, mid, adj_matrix, keep_edges)
	root2 = power_root(mid + 1, r, adj_matrix, keep_edges)
	if adj_matrix[root1][root2] > 0:
		keep_edges[root1][root2] = 1
		new_root = root1
	else:
		keep_edges[root2][root1] = 1
		new_root = root2
	return new_root
T = int(input())
for t in range(T):
	n = int(input())
	adj_matrix = []
	for i in range(n):
		adj_matrix.append([0] * n)
	keep_edges = []
	for i in range(n):
		keep_edges.append([0] * n)
	for i in range(1, n * (n - 1) // 2 + 1):
		(u, v) = [int(vert) for vert in input().split(' ')]
		adj_matrix[u - 1][v - 1] = i
	if not n in powers_of_two:
		print(-1)
		continue
	power_root(0, n - 1, adj_matrix, keep_edges)
	answer = []
	for i in range(n):
		for j in range(n):
			if keep_edges[i][j] == 0 and adj_matrix[i][j] != 0:
				answer.append(adj_matrix[i][j])
	print(len(answer))
	if len(answer) > 0:
		print(*answer)