There is only little time left until the New Year! For that reason, Chef decided to make a present for his best friend. He made a connected and undirected simple graph with N$N$ vertices and M$M$ edges.
Since Chef does not like odd numbers and his friend does not like undirected graphs, Chef decided to direct each edge in one of two possible directions in such a way that the indegrees of all vertices of the resulting graph are even. The indegree of a vertex is the number of edges directed to that vertex from another vertex. As usual, Chef is busy in the kitchen, so you need to help him with directing the edges. Find one possible way to direct them or determine that it is impossible under the given conditions, so that Chef could bake a cake as a present instead.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and M$M$.
- M$M$ lines follow. For each i$i$ (1≤i≤M$1 \le i \le M$), the i$i$-th of these lines contains two space-separated integers ui$u_i$ and vi$v_i$ denoting an edge between vertices ui$u_i$ and vi$v_i$.

-----Output-----
For each test case:
- If a valid way to direct the edges does not exist, print a single line containing one integer −1$-1$.
- Otherwise, print a single line containing M$M$ space-separated integers. For each valid i$i$, the i$i$-th of these integers should be 0$0$ if edge i$i$ is directed from ui$u_i$ to vi$v_i$ or 1$1$ if it is directed from vi$v_i$ to ui$u_i$.

-----Constraints-----
- 1≤T≤5$1 \le T \le 5$
- 1≤N,M≤105$1 \le N, M \le 10^5$
- 1≤ui,vi≤N$1 \le u_i, v_i \le N$ for each valid i$i$
- the graph on the input is connected, does not contain multiple edges or self-loops

-----Subtasks-----
Subtask #1 (30 points): 1≤N,M≤1,000$1 \le N, M \le 1,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4 4
1 2
1 3
2 4
3 4
3 3
1 2
2 3
1 3

-----Example Output-----
0 0 1 1
-1

Difficulty: HARD
Tags: Dynamic programming

Graph algorithms

Graph traversal
Skill types: Dynamic programming

Starter code:

Solutions:
try:
	for __ in range(int(input())):
		(n, m) = map(int, input().split())
		g = [[] for _ in range(n + 1)]
		long = []
		di = {}
		stable = [0 for _ in range(n + 1)]
		edges = [0 for _ in range(m)]
		for i in range(m):
			(x, y) = map(int, input().split())
			g[x].append(y)
			g[y].append(x)
			stable[y] += 1
			long.append([x, y])
			di[x, y] = i
			di[y, x] = i
		f = 1
		if m % 2:
			f = 0
		for i in range(m):
			(c, d) = (long[i][0], long[i][1])
			if stable[c] % 2 == 1 and stable[d] % 2 == 1:
				stable[c] += 1
				stable[d] -= 1
				edges[i] = 1
		s = []
		for i in range(1, n + 1):
			if stable[i] % 2 == 1:
				s.append(i)
		while s and f:
			set1 = set()
			for i in s:
				if stable[i] % 2:
					y = g[i][0]
					w = di[i, y]
					stable[y] += 1
					stable[i] -= 1
					set1.add(y)
					edges[w] = abs(edges[w] - 1)
			s = set1
		if f:
			print(*edges)
		else:
			print(-1)
except:
	pass


from sys import stdin, stdout
from collections import defaultdict as dd
inp = lambda : (int(o) for o in stdin.readline().split())
for _ in range(*inp()):
	(n, m) = inp()
	graph = dd(list)
	l = []
	di = {}
	inc = [0] * (n + 1)
	k = [0] * m
	for i in range(m):
		(c, d) = inp()
		graph[c].append(d)
		graph[d].append(c)
		inc[d] += 1
		l.append([c, d])
		di[str(c) + '_' + str(d)] = i
		di[str(d) + '_' + str(c)] = i
	if m % 2:
		print(-1)
		continue
	for i in range(m):
		(c, d) = (l[i][0], l[i][1])
		if inc[c] % 2 and inc[d] % 2:
			inc[c] += 1
			inc[d] -= 1
			k[i] = 1
	stack = []
	for i in range(1, n + 1):
		if inc[i] % 2:
			stack.append(i)
	while stack:
		s = set()
		for i in stack:
			if inc[i] % 2:
				for j in graph[i]:
					x = di[str(i) + '_' + str(j)]
					if k[x]:
						inc[j] += 1
						inc[i] -= 1
					else:
						inc[i] += 1
						inc[j] -= 1
					s.add(j)
					k[x] = abs(k[x] - 1)
					break
		stack = s
	print(*k)


for _ in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	edges = [0] * M
	dir = {}
	nodes = [[] for j in range(N + 1)]
	ind = [0] * (N + 1)
	graph = {}
	final_edges = []
	for i in range(M):
		(u, v) = [int(x) for x in input().split()]
		nodes[u].append(v)
		nodes[v].append(u)
		dir[u, v] = 1
		dir[v, u] = 0
		ind[v] += 1
		graph[u, v] = graph[v, u] = i
		final_edges.append([u, v])
	if M % 2 != 0:
		print(-1)
		continue
	for i in range(M):
		(u, v) = final_edges[i]
		if ind[u] % 2 != 0 and ind[v] % 2 != 0:
			d = dir[u, v]
			if d:
				ind[u] += 1
				ind[v] -= 1
				dir[u, v] = 0
				dir[v, u] = 1
				edges[i] = abs(edges[i] - 1)
			else:
				ind[u] -= 1
				ind[v] += 1
				dir[u, v] = 1
				dir[v, u] = 0
				edges[i] = abs(edges[i] - 1)
	s = []
	for i in range(1, N + 1):
		if ind[i] % 2:
			s.append(i)
	while s:
		set1 = set()
		for u in s:
			if ind[u] % 2:
				v = nodes[u][0]
				d = dir[u, v]
				index = graph[u, v]
				set1.add(v)
				if d:
					ind[u] += 1
					ind[v] -= 1
					dir[u, v] = 1
					dir[v, u] = 1
					edges[index] = abs(edges[index] - 1)
				else:
					ind[u] -= 1
					ind[v] += 1
					dir[u, v] = 1
					dir[v, u] = 0
					edges[index] = abs(edges[index] - 1)
		s = set1
	print(*edges)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[] for i in range(n + 1)]
	b = [0] * (n + 1)
	k = [0] * m
	l = []
	di = {}
	for i in range(m):
		(c, d) = map(int, input().split())
		a[c].append(d)
		a[d].append(c)
		b[d] += 1
		l.append([c, d])
		di[str(c) + ' ' + str(d)] = i
		di[str(d) + ' ' + str(c)] = i
	if m % 2 == 1:
		print(-1)
		continue
	for i in range(m):
		(c, d) = (l[i][0], l[i][1])
		if b[c] % 2 == 1 and b[d] % 2 == 1:
			k[i] = 1
			b[c] += 1
			b[d] -= 1
	st = []
	for i in range(1, n + 1):
		if b[i] % 2 == 1:
			st.append(i)
	while st:
		l = set()
		for i in st:
			if b[i] % 2 == 1:
				for j in a[i]:
					x = di[str(i) + ' ' + str(j)]
					if k[x] == 0:
						b[i] += 1
						b[j] -= 1
					else:
						b[i] -= 1
						b[j] += 1
					l.add(j)
					k[x] = int(not k[x])
					break
		st = l
	print(*k)


for _ in range(int(input())):
	l = []
	mp = {}
	cr = {}
	ans = []
	(n, m) = map(int, input().split())
	for i in range(1, n + 1):
		mp[i] = 0
		cr[i] = False
	for _ in range(m):
		(f, t) = map(int, input().split())
		l.append((f, t, -1000))
		mp[f] += 1
		mp[t] += 1
	if m % 2 > 0:
		print(-1)
		continue
	else:
		for _ in range(m):
			cr[l[_][1]] = not cr[l[_][1]]
			ans.append(0)
		for _ in range(m - 1, -1, -1):
			if cr[l[_][1]] == True:
				cr[l[_][1]] = not True
				ans[_] = 1
				if cr[l[_][0]]:
					cr[l[_][0]] = False
				else:
					cr[l[_][0]] = True
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


t = int(input())
for z in range(t):
	(n, m) = map(int, input().split(' '))
	mp = {}
	cr = {}
	for i in range(1, n + 1):
		mp[i] = 0
		cr[i] = False
	l = list()
	for j in range(m):
		(n1, n2) = map(int, input().split(' '))
		l.append((n1, n2))
		mp[n1] += 1
		mp[n2] += 1
	if m % 2 > 0:
		print(-1)
		continue
	else:
		ans = []
		for i in range(m):
			cr[l[i][1]] = not cr[l[i][1]]
			ans.append(0)
		for i in range(m - 1, -1, -1):
			if cr[l[i][1]] == True:
				cr[l[i][1]] = False
				ans[i] = 1
				if cr[l[i][0]] == True:
					cr[l[i][0]] = False
				else:
					cr[l[i][0]] = True
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


import sys
from collections import deque
croot = dict()
setnumber = dict()

def finalroot(v):
	if croot[v] != v:
		v = finalroot(croot[v])
	return v

def union(v1, v2):
	r1 = finalroot(v1)
	r2 = finalroot(v2)
	if r1 != r2:
		if setnumber[r1] > setnumber[r2]:
			croot[r2] = r1
		else:
			croot[r1] = r2
			if setnumber[r1] == setnumber[r2]:
				setnumber[r2] += 1

def minspan(n, edges):
	finale = []
	edgecount = {}
	for i in range(n):
		edgecount[i + 1] = 0
		setnumber[i + 1] = 0
		croot[i + 1] = i + 1
	edges.sort()
	for e in edges:
		(u, v) = e
		if finalroot(u) != finalroot(v):
			edgecount[u] += 1
			edgecount[v] += 1
			finale.append((u, v))
			union(u, v)
	root = max(edgecount.keys(), key=lambda k: edgecount[k])
	return (set(finale), root)

def main():
	t = int(input())
	for i in range(t):
		(n, m) = [int(item) for item in input().split()]
		e = set()
		elist = []
		for i in range(m):
			(u, v) = [int(item) for item in input().split()]
			elist.append((u, v))
			e.add((u, v))
		(finale, root) = minspan(n, list(e))
		sroot = root
		tofix = e - finale
		indegree = {}
		for i in range(n):
			indegree[i + 1] = 0
		decided = set()
		for t in tofix:
			indegree[t[1]] += 1
			decided.add((t[0], t[1]))
		cf = {}
		pf = {}
		for i in range(n):
			cf[i + 1] = set()
			pf[i + 1] = set()
		for f in finale:
			(u, v) = f
			cf[u].add(v)
			cf[v].add(u)
		r = deque()
		r.append(root)
		while len(r) != 0:
			root = r.pop()
			for c in cf[root]:
				r.append(c)
				cf[c].remove(root)
				pf[c] = root
		q = deque([sroot])
		st = deque()
		while len(q) != 0:
			node = q.pop()
			st.append(node)
			for e in cf[node]:
				q.append(e)
		while len(st) != 0:
			c = st.pop()
			if c != sroot:
				p = pf[c]
				if indegree[c] % 2 == 0:
					decided.add((c, p))
					indegree[p] += 1
				else:
					decided.add((p, c))
					indegree[c] += 1
		possible = indegree[sroot] % 2 == 0
		if possible:
			ans = []
			for i in elist:
				if i in decided:
					ans.append(0)
				else:
					ans.append(1)
			print(*ans)
		else:
			print(-1)
	return 0
main()


import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 6)
lines = sys.stdin.readlines()
visited = []
cnt = []
edges = []
u = []
v = []
res = []

def dfs(i):
	visited[i] = True
	numodd = 0
	for j in range(len(edges[i])):
		ni = edges[i][j][0]
		if not visited[ni]:
			temp = dfs(ni)
			if temp % 2 == 1:
				numodd += 1
				res[edges[i][j][1]] = 1
	return numodd % 2 + cnt[i] % 2
ln = 0
t = int(lines[ln])
ln += 1
for _ in range(t):
	(n, m) = [int(x) for x in lines[ln].split()]
	ln += 1
	visited = [False for i in range(n)]
	cnt = [0 for i in range(n)]
	edges = [[] for i in range(n)]
	u = [0 for i in range(m)]
	v = [0 for i in range(m)]
	res = [0 for i in range(m)]
	for i in range(m):
		(u[i], v[i]) = [int(x) for x in lines[ln].split()]
		ln += 1
		u[i] -= 1
		v[i] -= 1
		cnt[v[i]] += 1
		edges[u[i]].append((v[i], i))
		edges[v[i]].append((u[i], i))
	if m % 2 == 1:
		print(-1)
		continue
	dfs(n // 2)
	print(*res)


class Graph:

	def __init__(obj, ver):
		obj.V = ver
		obj.graph = []

	def addEdge(obj, u, v, w):
		obj.graph.append([u, v, w])

	def find(obj, par, i):
		if par[i] == i:
			return i
		return obj.find(par, par[i])

	def union(obj, par, rnk, x, y):
		xr = obj.find(par, x)
		yr = obj.find(par, y)
		if rnk[xr] < rnk[yr]:
			par[xr] = yr
		elif rnk[xr] > rnk[yr]:
			par[yr] = xr
		else:
			par[yr] = xr
			rnk[xr] += 1

	def KruskalMST(obj):
		i = 0
		e = 0
		obj.graph = sorted(obj.graph, key=lambda item: item[2])
		par = []
		rnk = []
		for node in range(obj.V):
			par.append(node)
			rnk.append(0)
		while e < obj.V - 1:
			(u, v, w) = obj.graph[i]
			i = i + 1
			x = obj.find(par, u)
			y = obj.find(par, v)
			if x != y:
				e = e + 1
				result[u + 1, v + 1] = w
				obj.union(par, rnk, x, y)
for i in range(int(input())):
	tmp = input().split()
	N = int(tmp[0])
	M = int(tmp[1])
	g = Graph(N)
	k = 0
	result = {}
	test = {}
	ans = []
	cnt = {}
	pos = {}
	idegree = {}
	for j in range(M):
		ans.append(-1)
		tmp = input().split()
		pos[int(tmp[0]), int(tmp[1])] = k
		g.addEdge(int(tmp[0]) - 1, int(tmp[1]) - 1, k)
		k += 1
	if M % 2:
		print('-1')
	else:
		g.KruskalMST()
		for j in range(N):
			test[j + 1] = []
			cnt[j + 1] = 0
			idegree[j + 1] = 0
		hash = {}
		for j in pos:
			try:
				x = result[j]
			except:
				idegree[j[1]] += 1
				ans[pos[j]] = 0
		for j in result:
			test[j[0]].append(j[1])
			test[j[1]].append(j[0])
			cnt[j[0]] += 1
			cnt[j[1]] += 1
			hash[j[0]] = 1
			hash[j[1]] = 1
		queue = []
		for j in cnt:
			if cnt[j] == 1:
				queue.append(j)
				hash[j] = 0
		c = len(result)
		while c > 0:
			f = 1
			x = queue.pop(0)
			for j in test[x]:
				if hash[j]:
					y = j
					break
			cnt[y] -= 1
			if cnt[y] == 1:
				queue.append(y)
				hash[y] = 0
			if idegree[x] % 2 == 0:
				idegree[y] += 1
				try:
					ans[pos[x, y]] = 0
				except:
					ans[pos[y, x]] = 1
			else:
				try:
					ans[pos[x, y]] = 1
				except:
					ans[pos[y, x]] = 0
			c -= 1
			ll = y
		if idegree[ll] % 2:
			f = 0
		else:
			f = 1
		if f:
			for j in ans:
				print(j, end=' ')
			print()
		else:
			print('-1')


from collections import deque
from heapq import *
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [set() for i in range(n)]
	newgraph = [set() for i in range(n)]
	edges = []
	for i in range(m):
		(ui, vi) = map(int, input().split())
		edges.append((ui - 1, vi - 1))
		graph[ui - 1].add(vi - 1)
		graph[vi - 1].add(ui - 1)
	if m & 1:
		print(-1)
		continue
	nodes = [(len(graph[i]), -i) for i in range(n)]
	indegs = [0] * n
	heapify(nodes)
	while nodes:
		(l, node) = heappop(nodes)
		node = -1 * node
		clist = list(graph[node])
		graph[node] = set()
		for cnode in clist:
			if indegs[node] & 1:
				newgraph[cnode].add(node)
				indegs[node] += 1
			else:
				newgraph[node].add(cnode)
				indegs[cnode] += 1
			graph[cnode].remove(node)
			heappush(nodes, (len(graph[cnode]), -cnode))
	ans = []
	for (ui, vi) in edges:
		if ui in newgraph[vi]:
			ans.append(1)
		else:
			ans.append(0)
	print(*ans)


T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	tab = dict()
	sasiedzi = [[] for i in range(N)]
	wchodzs = [[] for i in range(N)]
	visited = [-1] * N
	kraws = []
	for m in range(M):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		kraws.append((x, y))
		tab[x, y] = 1
		tab[y, x] = 1
		sasiedzi[x].append(y)
		sasiedzi[y].append(x)
	for vis in range(N):
		if visited[vis] >= 0:
			continue
		krawedzi = set()
		stack = [vis]
		visited[vis] = 0
		ind = 0
		while stack:
			nr = stack[-1]
			bylo = []
			for j in range(visited[nr], len(sasiedzi[nr])):
				i = sasiedzi[nr][j]
				if visited[i] >= 0:
					continue
				stack.append(i)
				visited[nr] = j + 1
				visited[i] = 0
				bylo = True
				break
			if bylo:
				continue
			stack.pop()
			if not stack:
				break
			wchodzacych = 0
			nieustalonych = 0
			for i in sasiedzi[nr]:
				if tab[nr, i] == -1:
					wchodzacych += 1
				if tab[nr, i] == tab[i, nr]:
					nieustalonych += 1
					nieustnr = i
			if nieustalonych == 1:
				if wchodzacych % 2 == 0:
					tab[nieustnr, nr] = -1
				else:
					tab[nr, nieustnr] = -1
			else:
				for i in sasiedzi[nr]:
					if nieustalonych == 0:
						break
					if tab[nr, i] != tab[i, nr]:
						continue
					if nieustalonych == 1 and wchodzacych % 2 == 0:
						tab[i, nr] = -1
						nieustalonych -= 1
						break
					tab[nr, i] = -1
					nieustalonych -= 1
					wchodzacych += 1
		if len(krawedzi) % 2 == 1:
			niepa = True
	res = [0] * M
	nr = 0
	for (x, y) in kraws:
		if tab[x, y] == -1:
			res[nr] = 1
		nr += 1
	ok = True
	for y in range(N):
		chk = 0
		for sas in sasiedzi[y]:
			if tab[y, sas] == -1:
				chk += 1
		if chk % 2 != 0:
			ok = False
	if ok:
		print(' '.join(map(str, res)))
	else:
		print(-1)


from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
global edgesdone

def f():
	sys.stdout.flush()

def solve(key, nodes, track, result):
	node = nodes[key]
	track[key] = 1
	tmpindg = 0
	global edgesdone
	for sub in node:
		(k, s) = (int(key), int(sub))
		if track.get(sub, 0) == 0:
			edgesdone += 1
			indg = solve(sub, nodes, track, result)
			if indg == 0:
				result[k][s] = '1'
				result[s][k] = '0'
				tmpindg ^= 1
			else:
				result[k][s] = '0'
				result[s][k] = '1'
		elif track[sub] == 2:
			result[k][s] = '1'
			result[s][k] = '0'
			tmpindg ^= 1
			edgesdone += 1
		else:
			nodes[sub].append(key)
	track[key] = 2
	return tmpindg
tests = int(input())
result = defaultdict(lambda : defaultdict(int))
for t in range(tests):
	edgesdone = 0
	(n, m) = map(int, input().split())
	if m % 2 == 1:
		for i in range(m):
			tmp = input()
		print(-1)
	else:
		nodes = {}
		track = {}
		order = []
		for i in range(0, m):
			(v1, v2) = sys.stdin.readline().split()
			if i == 0:
				startkey = v1
			n1 = nodes.get(v1)
			n2 = nodes.get(v2)
			if n1 is None:
				if n2 is None:
					nodes[v1] = [v2]
					nodes[v2] = []
				else:
					n2.append(v1)
					nodes[v2] = n2
					nodes[v1] = []
			else:
				n1.append(v2)
				nodes[v1] = n1
				if n2 is None:
					nodes[v2] = []
			order.append((int(v1), int(v2)))
		tmp = solve(startkey, nodes, track, result)
		res = []
		for query in order:
			res.append(result[query[0]][query[1]])
		print(' '.join(res))
	f()


t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	edges = [[0] * 2 for i in range(m)]
	degrees = [0] * (n + 1)
	dgcp = [0] * (n + 1)
	ans = [0] * m
	less = [-1] * (n + 1)
	great = [-1] * (n + 1)
	for i in range(m):
		(u, v) = map(int, input().split())
		edges[i] = [u, v]
		if u > v:
			if great[v] == -1:
				great[v] = i
			if less[u] == -1:
				less[u] = i
		else:
			if great[u] == -1:
				great[u] = i
			if less[v] == -1:
				less[v] = i
		degrees[v] += 1
		dgcp[v] += 1
	flag = 1
	for i in range(1, n):
		if degrees[i] % 2 != 0:
			j = great[i]
			if j > -1:
				if edges[j][1] == i and edges[j][0] > i:
					degrees[i] -= 1
					degrees[edges[j][0]] += 1
					ans[j] = 1
				elif edges[j][1] > i and edges[j][0] == i:
					degrees[i] += 1
					degrees[edges[j][1]] -= 1
					ans[j] = 1
		if degrees[i] % 2 != 0:
			flag = 0
	if degrees[n] % 2 == 0 and flag == 1:
		str1 = ' '.join((str(e) for e in ans))
		print(str1)
	else:
		ans = [0] * m
		flag = 1
		for i in range(n, 1, -1):
			if dgcp[i] % 2 != 0:
				j = less[i]
				if j > -1:
					if edges[j][1] == i and edges[j][0] < i:
						dgcp[i] -= 1
						dgcp[edges[j][0]] += 1
						ans[j] = 1
					elif edges[j][1] < i and edges[j][0] == i:
						dgcp[i] += 1
						dgcp[edges[j][1]] -= 1
						ans[j] = 1
			if dgcp[i] % 2 != 0:
				flag = 0
		if dgcp[1] % 2 == 0 and flag == 1:
			str1 = ' '.join((str(e) for e in ans))
			print(str1)
		else:
			print(-1)


def make_it_even(p):
	if indegree[p] % 2 == 0:
		if p in parent:
			indegree[parent[p]] += 1
			graph[parent[p]].remove(p)
	elif p in parent:
		indegree[p] += 1
		graph[p].remove(parent[p])

def recurse(p):
	if len(child[p]) == 0:
		make_it_even(p)
		return
	for c in child[p]:
		recurse(c)
	make_it_even(p)
from collections import deque

def solve():
	vis = [False for i in range(n + 1)]
	q = deque()
	root = 1
	q.append(root)
	vis[root] = True
	while len(q) != 0:
		u = q.popleft()
		child[u] = set()
		for v in graph[u]:
			if not vis[v]:
				child[u].add(v)
				parent[v] = u
				vis[v] = True
				q.append(v)
	for k in range(1, n + 1):
		par = set()
		if k in parent:
			par.add(parent[k])
		remain = graph[k] - child[k] - par
		for each in remain:
			indegree[each] += 1
			graph[each].remove(k)
	recurse(root)
	if indegree[root] % 2 != 0:
		print(-1)
		return False
	return True
parent = dict()
child = dict()
n = m = 0
indegree = None
graph = None
for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	graph = [set() for i in range(n + 1)]
	order = []
	indegree = [0 for i in range(n + 1)]
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		order.append((u, v))
		graph[u].add(v)
		graph[v].add(u)
	if solve():
		for i in order:
			if i[1] in graph[i[0]]:
				print(0, end=' ')
			else:
				print(1, end=' ')
		print()


import time
import sys
import gc
from collections import deque

class Graph(object):

	def __init__(self, N, M):
		self.N = N
		self.M = M
		self.vec = {}
		self.edgeDirs = [0] * self.M
		self.spanning_edges = {}
		self.edge2index = {}
		self.index = 0

	def addEdge(self, u, v):
		if u not in self.vec:
			self.vec[u] = set()
		self.vec[u].add(v)
		if v not in self.vec:
			self.vec[v] = set()
		self.vec[v].add(u)
		self.edge2index[u, v] = self.index
		self.index += 1

	def makeEven(self):
		post_order = []
		stack = [1]
		visited = set()
		while len(stack) != 0:
			u = stack.pop()
			if u in visited:
				continue
			else:
				visited.add(u)
				post_order.append(u)
			for v in self.vec[u]:
				if v not in visited:
					self.spanning_edges[v] = u
					stack.append(v)
		while len(post_order) != 0:
			u = post_order.pop()
			odd_edges = len(self.vec[u]) % 2 == 1
			if odd_edges:
				span_node = self.spanning_edges[u]
				self.vec[u].remove(span_node)
			while len(self.vec[u]) > 0:
				v1 = self.vec[u].pop()
				v2 = self.vec[u].pop()
				self.direct(v1, u)
				self.direct(v2, u)
				self.vec[v1].remove(u)
				self.vec[v2].remove(u)
			if odd_edges:
				self.vec[u].add(span_node)

	def direct(self, u, v):
		if (u, v) not in self.edge2index:
			self.edgeDirs[self.edge2index[v, u]] = 1

	def getIndex(self, edge):
		(u, v) = edge
		if (u, v) in self.edge2index:
			return self.edge2index[u, v]
		else:
			return self.edge2index[v, u]
T = int(input())
for _ in range(T):
	[N, M] = list(map(int, input().split()))
	if M & 1:
		for _ in range(M):
			input()
		print(-1)
		sys.stdout.flush()
	else:
		graph = Graph(N, M)
		for _ in range(M):
			[ui, vi] = list(map(int, input().split()))
			graph.addEdge(ui, vi)
		graph.makeEven()
		print(' '.join(map(str, graph.edgeDirs)))
		sys.stdout.flush()


t = int(input())

def bfsorder(vertex, s, n):
	vl = []
	visited = {}
	queue = []
	queue.append(s)
	visited[s] = True
	while queue:
		s = queue.pop(0)
		vl.append(s)
		for i in vertex[s].edges:
			try:
				a = visited[i]
			except:
				queue.append(i)
				visited[i] = True
	return vl

def maxin(vertex, n):
	m = -1
	index = -1
	for i in range(n):
		if vertex[i].degree > m:
			m = vertex[i].degree
			index = i
	return index

def minlist(vertex, n):
	v = []
	m = 200000
	for i in range(n):
		if vertex[i].remedges < m:
			v = [i]
			m = vertex[i].remedges
		elif vertex[i].remedges == m:
			v.append(i)
	return v

class Vertex:

	def __init__(self):
		self.degree = 0
		self.confirmeddeg = 0
		self.out = {}
		self.edges = []
		self.remedges = 0
for _ in range(t):
	edgelist = []
	(n, m) = map(int, input().split())
	vertex = []
	vertex1 = []
	if m % 2 == 1:
		for i in range(m):
			(u, v) = map(int, input().split())
		print(-1)
		continue
	for _ in range(n):
		vertex.append(Vertex())
		vertex1.append(Vertex())
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		edgelist.append([u, v])
		vertex[u].degree += 1
		vertex[u].remedges += 1
		vertex[u].edges.append(v)
		vertex[v].degree += 1
		vertex[v].remedges += 1
		vertex[v].edges.append(u)
		vertex1[u].degree += 1
		vertex1[u].remedges += 1
		vertex1[u].edges.append(v)
		vertex1[v].degree += 1
		vertex1[v].remedges += 1
		vertex1[v].edges.append(u)
	vl = minlist(vertex, n)
	c = 0
	while c < n:
		for v in vl:
			flag = 0
			if vertex[v].remedges % 2 != vertex[v].confirmeddeg % 2:
				try:
					i = vertex[v].edges[0]
				except:
					flag = 1
					break
				vertex[v].out[i] = 1
				vertex[i].out[v] = 0
				vertex[i].edges.remove(v)
				vertex[i].remedges -= 1
				vertex[i].confirmeddeg += 1
				vertex[v].edges.remove(i)
			for i in vertex[v].edges:
				vertex[v].out[i] = 0
				vertex[i].out[v] = 1
				vertex[i].remedges -= 1
				vertex[i].edges.remove(v)
			vertex[v].remedges = 200000
			c += 1
		if flag == 1:
			break
		vl = minlist(vertex, n)
	if c == n:
		for i in edgelist:
			if vertex[i[0]].out[i[1]] == 1:
				print(0, end=' ')
			else:
				print(1, end=' ')
		print()
	else:
		vertex = vertex1
		v = maxin(vertex, n)
		vl = bfsorder(vertex, v, n)
		for k in range(n):
			v = vl[n - k - 1]
			if vertex[v].remedges % 2 != vertex[v].confirmeddeg % 2:
				i = vertex[v].edges[0]
				vertex[v].out[i] = 1
				vertex[i].out[v] = 0
				vertex[i].edges.remove(v)
				vertex[i].remedges -= 1
				vertex[i].confirmeddeg += 1
				del vertex[v].edges[0]
			for i in vertex[v].edges:
				vertex[v].out[i] = 0
				vertex[i].out[v] = 1
				vertex[i].remedges -= 1
				vertex[i].edges.remove(v)
		if True:
			for i in edgelist:
				if vertex[i[0]].out[i[1]] == 1:
					print(0, end=' ')
				else:
					print(1, end=' ')
			print()
		else:
			print(-1)


import sys
sys.setrecursionlimit(20000)

def leftedges(v):
	arr = []
	for i in dic[v]:
		if ans.get(str(i) + '-' + str(v), -1) == None or ans.get(str(v) + '-' + str(i), -1) == None:
			arr.append(i)
	return arr

def dfs(v, visited, ans, dic, check):
	visited[v] = True
	for i in dic[v]:
		if visited[i] == False:
			dfs(i, visited, ans, dic, check)
	arr = leftedges(v)
	l = len(arr)
	if l == 0:
		return
	elif l % 2 == 1 and check[v] % 2 == 0:
		a = arr[-1]
		if ans.get(str(v) + '-' + str(a), -1) == None:
			ans[str(v) + '-' + str(a)] = 0
		else:
			ans[str(a) + '-' + str(v)] = 1
		check[a] += 1
		check[v] += l - 1
		for j in range(l - 1):
			a = arr[j]
			if ans.get(str(a) + '-' + str(v), -1) == None:
				ans[str(a) + '-' + str(v)] = 0
			else:
				ans[str(v) + '-' + str(a)] = 1
	elif l % 2 == 1 and check[v] % 2 == 1:
		check[v] += l
		for j in range(l):
			a = arr[j]
			if ans.get(str(a) + '-' + str(v), -1) == None:
				ans[str(a) + '-' + str(v)] = 0
			else:
				ans[str(v) + '-' + str(a)] = 1
	elif l % 2 == 0 and check[v] % 2 == 1:
		a = arr[-1]
		if ans.get(str(v) + '-' + str(a), -1) == None:
			ans[str(v) + '-' + str(a)] = 0
		else:
			ans[str(a) + '-' + str(v)] = 1
		check[a] += 1
		check[v] += l - 1
		for j in range(l - 1):
			a = arr[j]
			if ans.get(str(a) + '-' + str(v), -1) == None:
				ans[str(a) + '-' + str(v)] = 0
			else:
				ans[str(v) + '-' + str(a)] = 1
	elif l % 2 == 0 and check[v] % 2 == 0:
		check[v] += l
		for j in range(l):
			a = arr[j]
			if ans.get(str(a) + '-' + str(v), -1) == None:
				ans[str(a) + '-' + str(v)] = 0
			else:
				ans[str(v) + '-' + str(a)] = 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dic = {i: [] for i in range(1, n + 1)}
	ans = {}
	for i in range(m):
		(u, v) = map(int, input().split())
		dic[u].append(v)
		dic[v].append(u)
		ans[str(u) + '-' + str(v)] = None
	if m % 2 == 1:
		print(-1)
	else:
		visited = {i: False for i in range(1, n + 1)}
		check = {i: 0 for i in range(1, n + 1)}
		dfs(1, visited, ans, dic, check)
		print(*ans.values())


cs = int(input())
for c in range(cs):
	(N, M) = map(int, input().split())
	vertices = []
	answer = []
	for n in range(N):
		parent = None
		children = set()
		neighbours = set()
		inEdges = set()
		outEdges = set()
		vertices.append([parent, children, neighbours, inEdges, outEdges])
	for m in range(M):
		(u, v) = map(int, input().split())
		answer.append([[u, v], None])
		vertices[u - 1][2].add(v)
		vertices[v - 1][2].add(u)
	inTree = set([1])
	levels = [[1]]
	while len(inTree) < N:
		curLeaves = levels[-1]
		nextL = []
		for leaf in curLeaves:
			for neigh in vertices[leaf - 1][2]:
				if neigh not in inTree:
					inTree.add(neigh)
					vertices[leaf - 1][1].add(neigh)
					vertices[neigh - 1][0] = leaf
					nextL.append(neigh)
		levels.append(nextL)
	for a in answer:
		u = a[0][0]
		v = a[0][1]
		if v not in vertices[u - 1][1] and v != vertices[u - 1][0]:
			vertices[u - 1][4].add(v)
			vertices[v - 1][3].add(u)
			a[1] = 0
	while len(levels) > 1:
		curLevel = levels.pop()
		for leafPointer in curLevel:
			parentPointer = vertices[leafPointer - 1][0]
			if len(vertices[leafPointer - 1][3]) % 2 == 0:
				vertices[leafPointer - 1][4].add(parentPointer)
				vertices[parentPointer - 1][3].add(leafPointer)
			else:
				vertices[leafPointer - 1][3].add(parentPointer)
				vertices[parentPointer - 1][4].add(leafPointer)
	root = levels.pop()[0]
	for a in answer:
		u = a[0][0]
		v = a[0][1]
		status = a[1]
		if status == None:
			uInEdges = vertices[u - 1][3]
			if v in uInEdges:
				a[1] = 1
			else:
				a[1] = 0
	if len(vertices[root - 1][3]) % 2 == 1:
		print(-1)
	else:
		for a in answer:
			print(a[1], end=' ')
		print()


import sys

def fprint(x):
	print(x, flush=True)

def qprint(x):
	sys.stdout.write(str(x) + '\n')

def input():
	return sys.stdin.readline()
import itertools
t = int(input())

class vertex:

	def __init__(self, id):
		self.num = id
		self.connections = []
		self.treeConnections = []
		self.inDeg = 0
		self.included = False
for _ in range(t):
	(N, M) = map(int, input().split())
	if M % 2:
		for x in range(M):
			(n, m) = map(int, input().split())
		print('-1')
	else:
		edges = []
		for x in range(M):
			edges.append([0, 0])
		vertices = []
		for i in range(0, N + 1):
			vertices.append(vertex(i))
		for x in range(M):
			(edges[x][0], edges[x][1]) = map(int, input().split())
			vertices[edges[x][0]].connections.append([edges[x][1], x])
			vertices[edges[x][1]].connections.append([edges[x][0], x])
		answer = list(itertools.repeat(-1, M))
		inST = list(itertools.repeat(0, M))
		queue = [1]
		vertices[1].included = True
		stack = [1]
		while len(queue) != 0:
			cur_ver = queue.pop()
			for conn in vertices[cur_ver].connections:
				if not vertices[conn[0]].included:
					vertices[cur_ver].treeConnections.append(conn)
					queue.append(conn[0])
					stack.append(conn[0])
					vertices[conn[0]].included = True
					inST[conn[1]] = 1
		for (index, edge) in enumerate(edges):
			if not inST[index]:
				answer[index] = 1
				vertices[edge[0]].inDeg += 1
		for ind in range(len(stack) - 1, -1, -1):
			cur_ver = stack[ind]
			for conn in vertices[cur_ver].treeConnections:
				(index, edge) = (conn[1], edges[conn[1]])
				if vertices[conn[0]].inDeg % 2:
					vertices[conn[0]].inDeg += 1
					if cur_ver == edge[0]:
						answer[index] = 0
					else:
						answer[index] = 1
				else:
					vertices[cur_ver].inDeg += 1
					if cur_ver == edge[0]:
						answer[index] = 1
					else:
						answer[index] = 0
		print(' '.join(map(str, answer)))


import sys
from collections import deque

def minspan(n, edges):
	nodelist = []
	finale = []
	for i in range(n):
		nodelist.append(set([i + 1]))
	for e in edges:
		u = e[0]
		v = e[1]
		for each_set in nodelist:
			if u in each_set:
				save1 = each_set
			if v in each_set:
				save2 = each_set
		if save1 != save2:
			finale.append((u, v))
			merged = save1 | save2
			nodelist.remove(save1)
			nodelist.remove(save2)
			nodelist.append(merged)
		if len(nodelist) == 1:
			break
	return finale

def main():
	t = int(input())
	for i in range(t):
		(n, m) = [int(item) for item in input().split()]
		e = set()
		elist = []
		for i in range(m):
			(u, v) = [int(item) for item in input().split()]
			elist.append((u, v))
			e.add((u, v))
		finale = set(minspan(n, e))
		tofix = e - finale
		indegree = {}
		for i in range(n):
			indegree[i + 1] = 0
		decided = set()
		for t in tofix:
			indegree[t[1]] += 1
			decided.add((t[0], t[1]))
		cf = {}
		pf = {}
		for i in range(n):
			cf[i + 1] = set()
			pf[i + 1] = set()
		for f in finale:
			cf[f[0]].add(f[1])
			cf[f[1]].add(f[0])
		root = 1
		visit = set([root])
		visited = set()
		parent = {}
		while len(visited) < n and len(visit) > 0:
			v = visit.pop()
			d = cf[v]
			visited.add(v)
			for i in d:
				if i not in visited:
					parent[i] = v
					pf[v].add(i)
					visit.add(i)
		leaf = set()
		for (k, v) in cf.items():
			if len(v) == 1:
				leaf.add(k)
		st = [1]
		sc = [1]
		while len(st) < n + 1:
			if len(sc) == 0:
				break
			j = sc.pop()
			for i in pf[j]:
				st.append(i)
				sc.append(i)
		while len(st) != 1:
			g = st.pop()
			h = parent[g]
			pair1 = (g, h)
			pair2 = (h, g)
			if indegree[g] % 2 == 0:
				decided.add(pair1)
				indegree[h] += 1
			else:
				decided.add(pair2)
				indegree[g] += 1
		possible = indegree[root] % 2 == 0
		if possible:
			ans = []
			for i in elist:
				if i in decided:
					ans.append(0)
				else:
					ans.append(1)
			print(*ans)
		else:
			print(-1)
	return 0

def __starting_point():
	main()
__starting_point()


class Node:

	def __init__(self, ID):
		self.indegree = 0
		self.outdegree = 0
		self.nbrs = dict()
		self.STchildren = 0
		self.toroot = None
		self.ID = ID
		self.tag = ''

	def __repr__(self):
		return str(self.ID) + '->' + repr(self.nbrs)

def readEdgeFor(g, e):
	(u, v) = map(int, input().split())
	g[u].outdegree += 1
	g[u].nbrs[v] = len(e)
	g[v].indegree += 1
	g[v].nbrs[u] = len(e)
	e.append((u, v))
for ti in range(int(input())):
	(n, m) = map(int, input().split())
	if 1 == m % 2:
		for _ in range(m):
			input()
		print(-1)
		continue
	tree = [Node(i) for i in range(n + 1)]
	edges = []
	for _ in range(m):
		readEdgeFor(tree, edges)
	root = tree[1]
	newnodes = [root]
	leaves = []
	while newnodes:
		wknodes = newnodes
		newnodes = []
		for a in wknodes:
			for nb in a.nbrs.keys():
				nn = tree[nb]
				if nn.tag == 'v':
					continue
				nn.tag = 'v'
				if nn.STchildren == 0:
					a.STchildren += 1
					nn.toroot = a
					newnodes.append(nn)
			if a.STchildren == 0:
				leaves.append(a)
	root.STchildren += 1
	dir = [0] * m
	for a in leaves:
		w = a
		while w.STchildren == 0:
			p = w.toroot
			if w.indegree % 2 == 1:
				dir[w.nbrs[p.ID]] = 1
				p.indegree += 1
			p.STchildren -= 1
			w = p
	print(*dir)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [[] for i in range(n)]
	l = []
	di = {}
	inc = [0] * n
	etc = [[] for i in range(500000)]
	k = [0] * m
	for i in range(m):
		(c, d) = map(int, input().split())
		graph[c - 1].append(d - 1)
		graph[d - 1].append(c - 1)
		inc[d - 1] += 1
		l.append([c - 1, d - 1])
		di[str(c - 1) + '-+-' + str(d - 1)] = i
		di[str(d - 1) + '-+-' + str(c - 1)] = i
	flag = 1
	if m % 2:
		flag = 0
	for i in range(m):
		(c, d) = (l[i][0], l[i][1])
		if inc[c] % 2 == 1 and inc[d] % 2 == 1:
			inc[c] += 1
			inc[d] -= 1
			k[i] = 1
	stack = []
	for i in range(0, n):
		if inc[i] % 2 == 1:
			stack.append(i)
	while stack and flag:
		s = set()
		for i in stack:
			if inc[i] % 2:
				j = graph[i][0]
				x = di[str(i) + '-+-' + str(j)]
				if k[x]:
					inc[j] += 1
					inc[i] -= 1
				else:
					inc[i] += 1
					inc[j] -= 1
				s.add(j)
				k[x] = abs(k[x] - 1)
		stack = s
	if flag:
		print(*k)
	else:
		print(-1)


from collections import OrderedDict
T = int(input())
for t in range(T):
	(N, M) = [int(x) for x in input().split()]
	if M % 2 == 1:
		for i in range(M):
			(i, j) = [int(x) for x in input().split()]
		print(-1)
	else:
		indegree = {k: 0 for k in list(range(1, N + 1))}
		d = {k: [] for k in list(range(1, N + 1))}
		edges = OrderedDict()
		for i in range(M):
			(i, j) = [int(x) for x in input().split()]
			d[i].append(j)
			edges[i, j] = 0
			indegree[j] = 1 - indegree[j]
		parent = [-1] * (N + 1)
		visited = {k: 0 for k in list(range(1, N + 1))}
		stack = []
		leaf = []
		stack.append(1)
		visited[1] = 1
		while stack:
			vertex = stack.pop()
			nochildren = 1
			for v in d[vertex]:
				if visited[v] == 0:
					stack.append(v)
					visited[v] = 1
					parent[v] = vertex
					nochildren = 0
			if nochildren == 1:
				leaf.append(vertex)
		for i in leaf:
			j = i
			while j != 1:
				dad = parent[j]
				if indegree[j] == 1:
					indegree[j] = 0
					indegree[dad] = 1 - indegree[dad]
					if (j, dad) in edges:
						edges[j, dad] = 1 - edges[j, dad]
					elif (dad, j) in edges:
						edges[dad, j] = 1 - edges[dad, j]
				j = dad
		if indegree[1] == 1:
			print(-1)
			continue
		ans = ''
		for (key, value) in edges.items():
			ans = ans + ' ' + str(value)
		print(ans.strip())


import sys
from collections import deque

def minspan(n, edges):
	nodelist = []
	finale = []
	edgecount = {}
	for i in range(n):
		edgecount[i + 1] = 0
	for i in range(n):
		nodelist.append(set([i + 1]))
	for e in edges:
		u = e[0]
		v = e[1]
		for each_set in nodelist:
			if u in each_set:
				save1 = each_set
			if v in each_set:
				save2 = each_set
		if save1 != save2:
			finale.append((u, v))
			edgecount[u] += 1
			edgecount[v] += 1
			merged = save1 | save2
			nodelist.remove(save1)
			nodelist.remove(save2)
			nodelist.append(merged)
		if len(nodelist) == 1:
			break
	root = max(edgecount.keys(), key=lambda k: edgecount[k])
	return (set(finale), root)

def main():
	t = int(input())
	for i in range(t):
		(n, m) = [int(item) for item in input().split()]
		e = set()
		elist = []
		for i in range(m):
			(u, v) = [int(item) for item in input().split()]
			elist.append((u, v))
			e.add((u, v))
		(finale, root) = minspan(n, e)
		sroot = root
		tofix = e - finale
		indegree = {}
		for i in range(n):
			indegree[i + 1] = 0
		decided = set()
		for t in tofix:
			indegree[t[1]] += 1
			decided.add((t[0], t[1]))
		cf = {}
		pf = {}
		for i in range(n):
			cf[i + 1] = set()
			pf[i + 1] = set()
		for f in finale:
			(u, v) = f
			cf[u].add(v)
			cf[v].add(u)
		r = deque()
		r.append(root)
		while len(r) != 0:
			root = r.pop()
			for c in cf[root]:
				r.append(c)
				cf[c].remove(root)
				pf[c] = root
		q = deque([sroot])
		st = deque()
		while len(q) != 0:
			node = q.pop()
			st.append(node)
			for e in cf[node]:
				q.append(e)
		while len(st) != 0:
			c = st.pop()
			if c != sroot:
				p = pf[c]
				if indegree[c] % 2 == 0:
					decided.add((c, p))
					indegree[p] += 1
				else:
					decided.add((p, c))
					indegree[c] += 1
		possible = indegree[sroot] % 2 == 0
		if possible:
			ans = []
			for i in elist:
				if i in decided:
					ans.append(0)
				else:
					ans.append(1)
			print(*ans)
		else:
			print(-1)
	return 0

def __starting_point():
	main()
__starting_point()


def find_edge_directions():
	if M % 2:
		return '-1'
	undirDict = {i: [] for i in range(N + 1)}
	degCtr = [0 for i in range(N + 1)]
	indegCtr = [0 for i in range(N + 1)]
	lenList = [[] for i in range(N + 1)]
	result = [None for i in range(M)]
	for i in range(M):
		undirDict[uvList[i][0]].append(uvList[i])
		undirDict[uvList[i][1]].append(uvList[i])
		degCtr[uvList[i][0]] += 1
		degCtr[uvList[i][1]] += 1
	for i in range(1, N + 1):
		lenList[len(undirDict[i])].append(i)
	(i, ctr) = (1, 0)
	while ctr < M:
		while i < 1 or lenList[i] == []:
			i += 1
		vert = lenList[i][0]
		if undirDict[vert] == []:
			del lenList[i][0]
			continue
		(u, v, idx) = undirDict[vert][0]
		if result[idx] != None:
			del undirDict[vert][0]
			continue
		elif u == vert and indegCtr[vert] % 2 or (v == vert and indegCtr[vert] % 2 == 0):
			result[idx] = '1'
			indegCtr[u] += 1
		else:
			result[idx] = '0'
			indegCtr[v] += 1
		del undirDict[vert][0]
		del lenList[i][0]
		lenList[i - 1].append(vert)
		if vert == v:
			lenList[degCtr[u] - 1].append(u)
		else:
			lenList[degCtr[v] - 1].append(v)
		(degCtr[u], degCtr[v]) = (degCtr[u] - 1, degCtr[v] - 1)
		i = i - 1
		ctr += 1
	return ' '.join(result)
T = int(input())
opList = []
for x in range(T):
	(N, M) = map(int, input().split())
	uvList = [list(map(int, input().split())) + [_] for _ in range(M)]
	opList.append(find_edge_directions())
print('\n'.join(opList))


class Nodes:

	def __init__(self, k, p, q):
		self.value = k
		self.next = None
		self.reverse = p
		self.edgenumber = q

class GraphNodes:

	def __init__(self, k):
		self.value = k
		self.next = None
		self.visited = 0

class AdjascencyList:

	def __init__(self, n):
		self.adj_lst = [None] * n
		for i in range(n):
			self.adj_lst[i] = GraphNodes(i)

	def insert(self, x, y, p, q):
		temp = Nodes(y, p, q)
		a = self.adj_lst[x]
		temp.next = a.next
		a.next = temp

def solve(G, Q, n, m):
	ans = [0 for i in range(m)]
	for i in range(n - 1, 0, -1):
		v = i
		if Q[v] == 0:
			a = G.adj_lst[v]
			while a.next != None:
				if G.adj_lst[a.next.value].visited == 0:
					ans[a.next.edgenumber] = a.next.reverse
					Q[a.next.value] = Q[a.next.value] ^ 1
				a = a.next
		else:
			a = G.adj_lst[v]
			counts = 0
			while a.next != None and counts == 0:
				if G.adj_lst[a.next.value].visited == 0:
					ans[a.next.edgenumber] = a.next.reverse ^ 1
					counts = 1
				a = a.next
			while a.next != None:
				if G.adj_lst[a.next.value].visited == 0:
					ans[a.next.edgenumber] = a.next.reverse
					Q[a.next.value] = Q[a.next.value] ^ 1
				a = a.next
		G.adj_lst[v].visited = 1
	return ans

def main():
	t = int(input())
	for p in range(t):
		(n, m) = input().split()
		(n, m) = (int(n), int(m))
		if m % 2 == 1:
			for i in range(m):
				(a, b) = input().split()
			print(-1)
		else:
			G = AdjascencyList(n)
			Q = [0 for i in range(n)]
			for i in range(m):
				(a, b) = input().split()
				(a, b) = (int(a) - 1, int(b) - 1)
				G.insert(a, b, 0, i)
				G.insert(b, a, 1, i)
			final = solve(G, Q, n, m)
			str1 = ' '.join((str(e) for e in final))
			print(str1)
main()