The Chef's latest idea is that some cooks might work better in pairs. So, he is going to experiment by pairing up some of his employees to see if the quality of the food prepared in his kitchen increases. However, only some pairs of employees are compatible. Two employees that are not compatible cannot be paired together.

For each pair of compatible employees, the Chef has assigned a number estimating how well the overall quality of the food might increase. Of course, each employee can only be paired with at most one other employee. Furthermore, it is ok to not pair some employees. So, your goal is to help the Chef decide how to pair the employees to maximize the total amount that the overall quality of food increases.

------ Input ------ 

The first line contains a single integer denoting the number of test cases (at most 50). Each test case begins with two integers n and m. Here, n is the number of employees (between 2 and 1000) and m is the number of compatible pairs of employees (between 1 and 10,000). The employees are numbered from 0 to n-1. The next m lines describe a pair of compatible employees, one per line. The i'th such line contains two distinct integers u_{i},v_{i} between 0 and n-1. Strangely enough, the Chef estimates that picking the i'th pair u_{i},v_{i} will increase the quality of food prepared in his kitchen by exactly 2^{i}.

No pair of employees will be given more than once in the input. That is, for distinct indices i and j, we do not have both u_{i} = u_{j} and v_{i} = v_{j}, nor do we have both u_{i} = v_{j} and v_{i} = u_{j}.

------ Output ------ 

The output for each test case consists of the indices of the pairs of employees that are used in a maximum total value pairing (the indices are between 0 and m-1). These indices should be given in increasing order with a single space between consecutive numbers. If there is more than one possible output, then any will do.

----- Sample Input 1 ------ 
2
4 5
0 1
1 2
2 3
1 3
3 0
4 3
0 1
2 3
2 1
----- Sample Output 1 ------ 
1 4
2

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
T = int(input())

def algo():
	(n, m) = map(int, input().split())
	li = []
	for i in range(m):
		v = set(list(map(int, input().split())))
		li.append(v)
	j = m - 1
	out = []
	vis = set()
	while j >= 0:
		if len(vis & li[j]) == 0:
			out.append(j)
			vis = vis | li[j]
			if len(vis) == n:
				break
		j -= 1
	for i in range(len(out)):
		print(out[len(out) - 1 - i], end=' ')
	print()
for i in range(T):
	algo()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ind = []
	pair = []
	for i in range(m):
		x = list(map(int, input().split()))
		pair.append(x)
	test = [pair[m - 1][0], pair[m - 1][1]]
	ind.append(m - 1)
	for i in range(m - 2, -1, -1):
		if pair[i][0] not in test and pair[i][1] not in test:
			ind.append(i)
			test.append(pair[i][0])
			test.append(pair[i][1])
	ind.reverse()
	print(*ind)


t = input()
for c in range(0, int(t)):
	(n, m) = input().split()
	emp = []
	for x in range(0, int(n)):
		emp.append(x)
	pair1 = []
	pair2 = []
	out = ''
	for y in range(0, int(m)):
		(u, v) = input().split()
		pair1.append(int(u))
		pair2.append(int(v))
	ret = []
	for z in range(int(m) - 1, -1, -1):
		if pair1[z] in emp and pair2[z] in emp:
			emp[pair1[z]] = -1
			emp[pair2[z]] = -1
			ret.append(z)
	ret.sort()
	for w in ret:
		out = out + str(w) + ' '
	print(out)


T = int(input())
for i in range(T):
	(n, m) = list(map(int, input().split()))
	dict_pairs = {}
	for i in range(m):
		dict_pairs[i] = list(map(int, input().split()))
	list_eff = []
	list_ind = []
	for j in range(m - 1, -1, -1):
		if dict_pairs[j][0] not in list_eff and dict_pairs[j][1] not in list_eff:
			list_ind.append(j)
			list_eff.append(dict_pairs[j][0])
			list_eff.append(dict_pairs[j][1])
	list_ind.sort()
	out = str(list_ind[0])
	for l in range(1, len(list_ind)):
		out = out + ' ' + str(list_ind[l])
	print(out)


T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	l = []
	q = []
	p = []
	for i in range(m):
		(k, x) = map(int, input().split())
		l.append([k, x])
	for i in reversed(range(m)):
		if l[i][0] not in q and l[i][1] not in q:
			q.append(l[i][0])
			q.append(l[i][1])
			p.append(i)
	p.sort()
	for i in range(len(p)):
		print(p[i], end=' ')
	print()


t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	a = []
	b = []
	for j in range(0, m):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	max = 0
	indices = []
	members = []
	sum = 0
	count = m
	for j in range(m - 1, -1, -1):
		if a[j] not in members and b[j] not in members:
			sum += 2 ** j
			members.append(a[j])
			members.append(b[j])
			indices.insert(0, j)
	for j in range(0, len(indices)):
		print(indices[j], end=' ')
	print()


for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	m = temp[1]
	used = []
	for i in range(n):
		used.append(0)
	ans = []
	pairs = []
	for i in range(m):
		pairs.append(list(map(int, input().split())))
	i = m - 1
	while i >= 0:
		a = pairs[i][0]
		b = pairs[i][1]
		if used[a] == 0 and used[b] == 0:
			ans.append(i)
			used[a] = 1
			used[b] = 1
		i -= 1
	i = len(ans) - 1
	while i >= 0:
		print(ans[i], end=' ')
		i -= 1
	print()


t = int(input())
for _ in range(t):
	(n, m) = (int(x) for x in input().split())
	a = {x for x in range(n)}
	s = []
	for i in range(m):
		s.append({int(x) for x in input().split()})
	result = []
	for (i, p) in reversed(list(enumerate(s))):
		if p.issubset(a):
			a -= p
			result.append(i)
	print(' '.join(map(str, sorted(result))))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cpls = []
	vis = [0] * n
	res = []
	for i in range(m):
		(a, b) = map(int, input().split())
		cpls.append([a, b])
	for i in range(m - 1, -1, -1):
		a = cpls[i][0]
		b = cpls[i][1]
		if vis[a] == 0 and vis[b] == 0:
			vis[a] = 1
			vis[b] = 1
			res.append(i)
	print(*reversed(res))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	freq = []
	res = [0 for _ in range(m)]
	arr = []
	for _ in range(m):
		arr.append(list(map(int, input().split())))
	i = m - 1
	while i >= 0:
		if arr[i][0] not in freq and arr[i][1] not in freq:
			res[i] = 1
			freq += arr[i]
		i -= 1
	ans = [i for i in range(m) if res[i] == 1]
	print(*ans)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	chef = []
	uchef = []
	result = []
	for i in range(m):
		(a, b) = map(int, input().split())
		chef.append(a)
		chef.append(b)
	uchef.append(chef[-1])
	uchef.append(chef[-2])
	result.append(len(chef) // 2 - 1)
	for i in range(0, len(chef), 2):
		if chef[-1 - i] not in uchef and chef[-1 - i - 1] not in uchef and (chef[-1 - i - 1] != chef[-1 - i]):
			uchef.append(chef[-1 - i])
			uchef.append(chef[-1 - i - 1])
			result.append((len(chef) - i) // 2 - 1)
	result = sorted(result)
	for i in range(len(result)):
		if i == len(result) - 1:
			print(result[i])
		else:
			print(result[i], end=' ')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = []
	c = []
	d = []
	while m:
		m -= 1
		a = list(map(int, input().split()))
		k.append(a)
	for i in range(len(k) - 1, -1, -1):
		if k[i][0] not in d and k[i][1] not in d:
			c.append(i)
			d.append(k[i][0])
			d.append(k[i][1])
	c.sort()
	for i in c:
		print(i, end=' ')
	print(' ')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = []
	for i in range(m):
		(u, v) = map(int, input().split())
		li.append([u, v])
	a = []
	b = []
	for i in range(m - 1, -1, -1):
		if li[i][0] not in b and li[i][1] not in b:
			b.extend([li[i][0], li[i][1]])
			a += [i]
		if len(a) == n // 2:
			break
	print(*sorted(a))


numberofcases = int(input())
for case in range(numberofcases):
	values = input().split(' ')
	employees = int(values[0])
	nopairs = int(values[1])
	pairs = []
	taken = []
	chosenpairs = []
	for pair in range(nopairs):
		pairs.append(input())
	for pair in reversed(pairs):
		ans = True
		for employee in pair.split(' '):
			if employee in taken:
				ans = False
		if ans:
			chosenpairs.append(str(pairs.index(pair)))
			taken = taken + pair.split(' ')
	print(' '.join(list(reversed(chosenpairs))))


T = int(input())
while T:
	(n, m) = map(int, input().split())
	k = m - 1
	ch = []
	l = []
	ans = []
	while m:
		t = tuple(map(int, input().split()))
		l.append(t)
		m -= 1
	while len(l) > 0:
		(x, y) = l.pop()
		if x not in ch and y not in ch:
			ch.append(x)
			ch.append(y)
			ans.append(k)
		k -= 1
	ans = ans[::-1]
	for _ in ans:
		print(_, end=' ')
	print('')
	T -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = []
	for i in range(m):
		(u, v) = map(int, input().split())
		li.append([u, v])
	c = [m - 1]
	j = [li[-1][0], li[-1][1]]
	for i in li[::-1][1:]:
		if i[0] not in j and i[1] not in j:
			j.extend([i[0], i[1]])
			c += [li.index(i)]
		if len(c) == n // 2:
			break
	print(*sorted(c))


def main():
	testCases = int(input())
	for _ in range(0, testCases):
		(numOfEmp, numOfComp) = [int(x) for x in input().split()]
		empArray = [0 for _ in range(0, numOfEmp)]
		pairArray = []
		resultArray = []
		for _ in range(0, numOfComp):
			pairArray.append([int(x) for x in input().split()])
		ind = len(pairArray) - 1
		while numOfEmp > 1 and ind >= 0:
			pair = pairArray[ind]
			if empArray[pair[0]] == 0 and empArray[pair[1]] == 0:
				empArray[pair[0]] = 1
				empArray[pair[1]] = 1
				resultArray.append(ind)
				numOfEmp = numOfEmp - 1
			ind = ind - 1
		while len(resultArray) > 1:
			print(resultArray.pop(), end=' ')
		print(resultArray.pop())
main()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	visited = []
	s = ''
	for j in range(m):
		(x, y) = map(int, input().split())
		l.append((x, y))
	for j in range(m - 1, -1, -1):
		a = l[j]
		if a[0] not in visited and a[1] not in visited:
			visited.append(a[0])
			visited.append(a[1])
			s = str(j) + ' ' + s
	print(s)


for j in range(int(input())):
	x = []
	(n, m) = map(int, input().split())
	for i in range(m):
		y = list(map(int, input().split()))
		x.append(y)
	x.reverse()
	(a, b) = (x[0][0], x[0][1])
	aman = [a, b]
	z = [m - 1]
	for i in x:
		if i[0] not in aman and i[1] not in aman:
			aman.append(i[0])
			aman.append(i[1])
			z.append(m - x.index(i) - 1)
	z.reverse()
	print(*z)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = []
	flag = []
	l = []
	for i in range(m):
		l.append(list(map(int, input().split())))
	ans.append(m - 1)
	flag.append(l[m - 1][0])
	flag.append(l[m - 1][1])
	for i in range(1, m):
		if l[m - 1 - i][0] not in flag and l[m - 1 - i][1] not in flag:
			ans.append(m - 1 - i)
			flag.append(l[m - 1 - i][0])
			flag.append(l[m - 1 - i][1])
	ans = sorted(ans)
	print(*ans)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	a = [0] * n
	l = []
	x = []
	for i in range(m):
		l.append(list(map(int, input().split())))
	for i in range(m - 1, -1, -1):
		if a[l[i][0]] == 0 and a[l[i][1]] == 0:
			a[l[i][0]] = 1
			a[l[i][1]] = 1
			x.append(i)
	x.reverse()
	print(*x)
	t -= 1


for x in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	b = []
	k = []
	ans = []
	for y in range(m):
		c = input().split(' ')
		a.append(int(c[0]))
		b.append(int(c[1]))
	t = m - 1
	while t != -1:
		if a[t] not in k and b[t] not in k:
			k.append(a[t])
			k.append(b[t])
			ans.append(t)
		t -= 1
	ans.sort()
	for y in ans:
		print(y, end=' ')
	print()


t = int(input())
for t0 in range(t):
	(n, m) = [int(i) for i in input().strip().split(' ')]
	li = []
	for i in range(m):
		li.append([int(j) for j in input().strip().split(' ')])
	st = [i for i in range(n)]
	ans = [m - 1]
	st.remove(li[m - 1][0])
	st.remove(li[m - 1][1])
	a = li[m - 1][0]
	b = li[m - 1][1]
	for i in range(m - 2, -1, -1):
		if not st:
			break
		(c, d) = li[i]
		if c in st and d in st:
			ans.append(i)
			st.remove(c)
			st.remove(d)
	ans.reverse()
	for i in ans:
		print(i, end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	chefdic = {}
	for i in range(n):
		chefdic[i] = i + 1
	pair_arr = []
	for i in range(m):
		temp = [int(j) for j in input().split()]
		pair_arr.append(temp)
	j = m
	full = n
	lis = []
	while j >= 0 and full > 0:
		if pair_arr[j - 1][0] in chefdic and pair_arr[j - 1][1] in chefdic:
			chefdic.pop(pair_arr[j - 1][0])
			chefdic.pop(pair_arr[j - 1][1])
			lis.append(j - 1)
			full -= 2
			j -= 1
		else:
			j -= 1
	lis.sort()
	for ele in lis:
		print(ele, end=' ')
	print('\n')


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	k = [0] * n
	l = []
	ans = []
	for i in range(m):
		l.append(list(map(int, input().split())))
	for i in range(m - 1, -1, -1):
		if k[l[i][0]] != 1 and k[l[i][1]] != 1:
			(k[l[i][0]], k[l[i][1]]) = (1, 1)
			ans.append(i)
	for i in range(len(ans) - 1, -1, -1):
		print(ans[i], end=' ')
	print()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	inc = []
	ans = []
	for j in range(m):
		arr.append(list(input().split()))
	inc.append(arr[-1][0])
	inc.append(arr[-1][1])
	for k in range(m - 2, -1, -1):
		if arr[k][0] not in inc and arr[k][1] not in inc:
			inc.append(arr[k][0])
			inc.append(arr[k][1])
			ans.append(k)
	ans.append(m - 1)
	ans.sort()
	for j in ans:
		print(j, end=' ')
	print()


for t in range(int(input())):
	(n, m) = map(int, input().split())
	pairs = []
	status = [0] * n
	selected = []
	for i in range(m):
		pairs.append(list(map(int, input().split())))
	i = m - 1
	while 0 in status and i >= 0:
		if status[pairs[i][0]] == 0 and status[pairs[i][1]] == 0:
			selected = [i] + selected[:]
			status[pairs[i][0]] = 1
			status[pairs[i][1]] = 1
		i -= 1
	print(*selected)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(m):
		a.append([])
	for i in range(m):
		(p1, p2) = map(int, input().split())
		a[i].append(p1)
		a[i].append(p2)
	a_n = [0] * n
	ans = []
	for i in range(m - 1, -1, -1):
		if a_n[a[i][0]] == 0 and a_n[a[i][1]] == 0:
			a_n[a[i][0]] = 1
			a_n[a[i][1]] = 1
			ans.append(i)
	for i in range(len(ans) - 1, -1, -1):
		print(ans[i], end=' ')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	pairs = []
	check = [0] * n
	ans = []
	for _ in range(m):
		(a, b) = map(int, input().split())
		pairs.append([a, b])
	i = m
	for x in pairs[::-1]:
		i -= 1
		if check[x[0]] == check[x[1]] == 0:
			(check[x[0]], check[x[1]]) = (1, 1)
			ans.append(i)
	print(*sorted(ans))


for _ in range(int(input())):
	(n, m) = [int(q) for q in input().split()]
	a = []
	for i in range(m):
		k = list(map(int, input().strip().split()))
		a.append(k)
	sol = []
	cd = []
	for j in range(m - 1, -1, -1):
		if a[j][0] not in cd and a[j][1] not in cd:
			sol.append(j)
			cd.append(a[j][0])
			cd.append(a[j][1])
	sol.sort()
	for k in range(len(sol)):
		print(sol[k], end=' ', sep=' ', flush=True)
	print()


for _ in range(int(input())):
	l = []
	(m, n) = map(int, input().split())
	for _ in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	l = l[::-1]
	(k, s) = ([], [])
	for i in range(n):
		if l[i][0] in k or l[i][1] in k:
			pass
		else:
			k.append(l[i][0])
			k.append(l[i][1])
			s.append(n - 1 - i)
	s.sort()
	print(*s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(m):
		a.append(list(map(int, input().split())))
	emp = []
	p = []
	for i in range(m - 1, -1, -1):
		if a[i][0] not in emp and a[i][1] not in emp:
			emp.append(a[i][0])
			emp.append(a[i][1])
			p.append(i)
	print(*sorted(p))


t = int(input())
for j in range(t):
	(n, m) = map(int, input().split())
	nlist = [i for i in range(n)]
	mlist = []
	for i in range(m):
		mlist.append(tuple(map(int, input().split())))
	mlist2 = mlist.copy()
	mlist.reverse()
	mselected = []
	for (x, y) in mlist:
		if x in nlist and y in nlist:
			nlist.remove(x)
			nlist.remove(y)
			mselected.append(mlist2.index((x, y)))
	p = ''
	for i in mselected:
		p = str(i) + ' ' + p
	print(p)


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	l = []
	for _ in range(m):
		l.append(tuple([int(i) for i in input().split()]))
	d = l.copy()
	l.reverse()
	done = []
	ans = []
	for i in l:
		if i[0] not in done and i[1] not in done:
			ans.append(d.index(i))
			done.append(i[0])
			done.append(i[1])
	ans.sort()
	for i in ans:
		print(i, end=' ')
	print()


try:
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		a = [0] * n
		l = []
		x = []
		for i in range(m):
			l.append(list(map(int, input().split())))
		for i in range(m - 1, -1, -1):
			if a[l[i][0]] == 0 and a[l[i][1]] == 0:
				a[l[i][0]] = 1
				a[l[i][1]] = 1
				x.append(i)
		x.reverse()
		print(*x)
except:
	pass


t = int(input())
while t:
	(n, m) = map(int, input().strip().split())
	a = []
	x = []
	y = []
	for i in range(m):
		a.append(list(map(int, input().strip().split())))
	a.reverse()
	for i in a:
		if i[0] in x or i[1] in x:
			continue
		else:
			x.append(i[0])
			x.append(i[1])
			y.append(m - a.index(i) - 1)
		if len(x) == n:
			break
	y.sort()
	for j in y:
		print(j, end=' ')
	print('')
	t -= 1


t = int(input())
for ni in range(t):
	(n, m) = map(int, input().split())
	l = []
	for nj in range(m):
		(a, b) = map(int, input().split())
		l.append([a, b])
	l1 = list()
	place = list()
	for i in range(m - 1, -1, -1):
		if l[i][0] not in l1 and l[i][1] not in l1:
			l1.append(l[i][0])
			l1.append(l[i][1])
			place.append(i)
	print(*sorted(place))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for x in range(m):
		arr.append(list(map(int, input().split())))
	s = []
	a = []
	for i in range(m - 1, -1, -1):
		if arr[i][0] not in s and arr[i][1] not in s:
			s.append(arr[i][0])
			s.append(arr[i][1])
			a.append(i)
	a.sort()
	print(*a)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	array = []
	used = [0] * N
	indices = []
	for i in range(M):
		(u, v) = map(int, input().split())
		array.append([u, v])
	for i in range(M - 1, -1, -1):
		a = array[i][0]
		b = array[i][1]
		if used[a] + used[b] == 0:
			indices.append(i)
			used[a] = 1
			used[b] = 1
	indices = indices[-1::-1]
	print(*indices)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	li = []
	added = []
	ct = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		li.append([x, y])
	l = len(li)
	i = 1
	while len(added) < n and i <= m:
		if li[-i][0] not in added and li[-i][1] not in added:
			added += li[-i]
			ct += [l - i]
		i += 1
	ct.sort()
	print(*ct)


t = int(input())
for val in range(0, t):
	(n, m) = map(int, input().split())
	l1 = []
	for va in range(0, m):
		(x, y) = map(int, input().split())
		l1.append(x)
		l1.append(y)
	l2 = []
	l3 = []
	l2.append(l1[len(l1) - 1])
	l2.append(l1[len(l1) - 2])
	l3.append(m - 1)
	s = m - 1
	for vb in range(len(l1) - 3, -2, -2):
		s = s - 1
		if l1[vb] not in l2 and l1[vb - 1] not in l2:
			l3.append(s)
			l2.append(l1[vb])
			l2.append(l1[vb - 1])
	l3.reverse()
	print(*l3)


for case in range(int(input())):
	(n, m) = map(int, input().split())
	pair = []
	chef = [False] * n
	for i in range(m):
		(u, v) = map(int, input().split())
		pair.append([u, v])
	final = []
	for i in range(m - 1, -1, -1):
		if not chef[pair[i][0]] and (not chef[pair[i][1]]):
			chef[pair[i][0]] = chef[pair[i][1]] = True
			final.insert(0, i)
	print(*final)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = []
	for _ in range(m):
		lst.append(list(map(int, input().split())))
	sel = []
	ans = []
	for i in range(m - 1, -1, -1):
		if lst[i][0] not in sel and lst[i][1] not in sel:
			sel.append(lst[i][0])
			sel.append(lst[i][1])
			ans.append(i)
	ans.sort()
	print(*ans)


tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	arr = []
	for j in range(m):
		arr.append(list(map(int, input().split())))
	selected = []
	ans = []
	for j in range(len(arr) - 1, -1, -1):
		if arr[j][0] not in selected and arr[j][1] not in selected:
			selected.append(arr[j][0])
			selected.append(arr[j][1])
			ans.append(j)
	ans.sort()
	print(*ans)


t = int(input())
for i in range(t):
	(n, m) = [int(n) for n in input().split()]
	x = []
	y = []
	z = []
	for j in range(m):
		(p1, p2) = [int(p1) for p1 in input().split()]
		x.append([p1, p2])
	for i in reversed(range(m)):
		if x[i][0] not in y and x[i][1] not in y:
			y.append(x[i][0])
			y.append(x[i][1])
			z.append(i)
	z.sort()
	for i in range(len(z)):
		print(z[i], end=' ')
	print()


for tc in range(int(input())):
	(N, M) = map(int, input().strip().split())
	p = []
	for i in range(M):
		(x, y) = map(int, input().strip().split())
		p.append((x, y))
	paired = [0] * N
	ans = []
	for i in range(M - 1, -1, -1):
		if paired[p[i][0]] == 0 and paired[p[i][1]] == 0:
			ans.append(i)
			paired[p[i][0]] = 1
			paired[p[i][1]] = 1
	for i in reversed(ans):
		print(i, end=' ')
	print()


t = int(input())
for count in range(t):
	(num_emps, num_pairs) = [int(x) for x in input().split(' ')]
	pairs = []
	used_pairs = []
	used_emps = set()
	for p in range(num_pairs):
		(e1, e2) = [int(x) for x in input().split(' ')]
		pairs.append((p, e1, e2))
	for (p, e1, e2) in pairs[::-1]:
		if e1 not in used_emps and e2 not in used_emps:
			used_pairs.append(p)
			used_emps.add(e1)
			used_emps.add(e2)
	print(' '.join((str(i) for i in used_pairs[::-1])))


t = int(input())
for i in range(0, t):
	(n, m) = input().strip().split()
	n = int(n)
	m = int(m)
	b = []
	a = []
	d = []
	for j in range(0, m):
		e = list(map(int, input().strip().split()))
		b.append(e)
	d.append(m - 1)
	a.append(b[m - 1][0])
	a.append(b[m - 1][1])
	for k in range(m - 2, -1, -1):
		if b[k][0] in a:
			z = 0
		elif b[k][1] in a:
			z = 0
		else:
			d.append(k)
			a.append(b[k][0])
			a.append(b[k][1])
	print(*d[::-1], sep=' ')


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(m):
		a.append(list(map(int, input().split())))
	emp = []
	pairindex = []
	for i in range(m - 1, -1, -1):
		if a[i][0] not in emp and a[i][1] not in emp:
			emp.append(a[i][0])
			emp.append(a[i][1])
			pairindex.append(i)
	print(*sorted(pairindex))


for i in range(int(input())):
	l = []
	visit = []
	s = ''
	(n, m) = map(int, input().split())
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		l.append([a, b])
	for i in range(m - 1, -1, -1):
		l1 = l[i]
		if l1[0] not in visit and l1[1] not in visit:
			visit.append(l1[0])
			visit.append(l1[1])
			s = str(i) + ' ' + s
	print(s)


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	l = []
	for __ in range(m):
		l.append([int(i) for i in input().split()])
	x = [m - 1]
	z = [l[m - 1][0], l[m - 1][1]]
	for i in range(m - 2, -1, -1):
		if l[i][0] not in z and l[i][1] not in z:
			z.append(l[i][0])
			z.append(l[i][1])
			x.append(i)
	x = x[::-1]
	for i in x:
		print(i, end=' ')
	print()


tes = int(input())
for g in range(tes):
	(n, m) = map(int, input().split())
	a = [[-1 for j in range(2)] for i in range(m)]
	for i in range(m):
		(a[i][0], a[i][1]) = map(int, input().split())
	emplis = []
	ans = []
	for i in range(n):
		emplis.append(i)
	track = len(a) - 1
	while track >= 0:
		if a[track][0] in emplis and a[track][1] in emplis:
			emplis.remove(a[track][0])
			emplis.remove(a[track][1])
			ans.append(track)
			track -= 1
		else:
			track -= 1
	ans = sorted(ans)
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	(employees, pairs) = map(int, input().split())
	matches = []
	for __ in range(pairs):
		matches.append(tuple(map(int, input().split())))
	matches = matches[::-1]
	A = []
	used = set()
	for (i, m) in enumerate(matches):
		if len(set(m) & used) == 0:
			A.append(pairs - i - 1)
			used |= set(m)
	A.sort()
	print(*A)


n = int(input())
for i in range(n):
	(n, m) = map(int, input().split())
	pairs = []
	for j in range(m):
		pairs.append(list(map(int, input().split())))
	employees = [False] * n
	count = []
	for j in range(m - 1, -1, -1):
		if not employees[pairs[j][0]] and (not employees[pairs[j][1]]):
			employees[pairs[j][0]] = True
			employees[pairs[j][1]] = True
			count.append(j)
	for j in range(len(count) - 1, -1, -1):
		print(count[j], end=' ')
	print()


t = int(input())
for I in range(t):
	(n, m) = [int(i) for i in input().split()]
	ind = []
	ha_sh = [0] * n
	a = []
	for i in range(m):
		b = [int(i) for i in input().split()]
		a.append(b)
	for i in range(len(a) - 1, -1, -1):
		if ha_sh[a[i][0]] == 0 and ha_sh[a[i][1]] == 0:
			ind.append(i)
			ha_sh[a[i][0]] = 1
			ha_sh[a[i][1]] = 1
	ind.sort()
	print(*ind)


from collections import deque
t = int(input())
for _ in range(t):
	(n, m) = [int(a) for a in input().strip().split()]
	N = [True] * n
	M = deque([])
	for i in range(m):
		(u, v) = [int(a) for a in input().strip().split()]
		M.append((u, v))
	list = []
	while m != 0:
		(u, v) = M.pop()
		if N[u] and N[v]:
			N[u] = False
			N[v] = False
			list.append(m - 1)
		m -= 1
	print(' '.join(map(str, reversed(list))))