Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a simple undirected graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges. He wants to divide it into $K$ parts (subgraphs) for some integer $K$.

First, Chef divides the vertices in the graph into $K$ sets such that each vertex belongs to exactly one set; the subgraphs and sets are numbered $1$ through $K$ such that for each valid $i$, vertices from the $i$-th set belong to the $i$-th subgraph. Then, Chef checks all the edges in the graph. For an edge connecting vertices $u$ and $v$, if $u$ and $v$ are both in the $i$-th set, then this edge belongs to the $i$-th subgraph. Otherwise, this edge does not belong to any of these $K$ subgraphs.

At the end, Chef checks these $K$ subgraphs. If each subgraph contains an even number of edges, then Chef thinks that this way of dividing the graph is *delicious*.

Chef wants to divide the graph in a delicious way such that $K$ is the smallest possible. Find the minimum $K$ and one such way to divide the graph.

------  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 two space-separated integers $N$ and $M$.
Each of the next $M$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.

------  Output ------
For each test case, print two lines. The first of these lines should contain a single integer ― the minimum $K$. The second line should contain $N$ space-separated integers, where for each valid $i$, the $i$-th integer denotes the subgraph that vertex $i$ belongs to.

If there are multiple solutions, you may output any one.

------  Constraints  ------
$1 ≤ T ≤ 3,000$
$1 ≤ M ≤ 100,000$
$2 ≤ N ≤ 100,000$
$1 ≤ u \neq v ≤ N$
the graph contains no duplicate edges or self-loops
the sum of $N$ over all test cases does not exceed $10^{6}$
the sum of $M$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 pts): $2 ≤ N ≤ 10$

Subtask #2 (70 pts): original constraints

----- Sample Input 1 ------ 
1
5 5
1 2
1 3
2 3
2 4
3 4
----- Sample Output 1 ------ 
2
1 2 1 1 2
----- explanation 1 ------ 
Example case 1: Subgraph $1$ contains vertices $1$, $3$, $4$ and edges $(1,3)$ and $(3,4)$. Subgraph $2$ contains vertices $2$ and $5$, but no edges.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
for _ in range(int(input())):
	(vertices, edges) = map(int, input().split())
	(deg, ans) = ([0] * (vertices + 1), [1] * vertices)
	for _ in range(edges):
		(v1, v2) = map(int, input().split())
		deg[v1] += 1
		deg[v2] += 1
	if edges % 2 == 0:
		print(1, '\n', *ans)
	else:
		flag = False
		for i in range(1, vertices + 1):
			if deg[i] % 2 != 0:
				(ans[i - 1], flag) = (2, True)
				break
		if flag:
			print(2, '\n', *ans)
		else:
			(ans[v1 - 1], ans[v2 - 1]) = (2, 3)
			print(3, '\n', *ans)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = [[]] * n
	d = [0] * n
	res = [1] * n
	for i in range(m):
		(u, v) = map(int, input().split())
		l[u - 1].append(v - 1)
		l[v - 1].append(u - 1)
		d[v - 1] += 1
		d[u - 1] += 1
	if m % 2 == 0:
		print(1)
		for i in range(n):
			print(1, end=' ')
		print()
		continue
	c = True
	for i in range(n):
		if d[i] % 2 == 1 and c:
			res[i] = 2
			c = False
		if d[i] == 0:
			res[i] = 2
	if c:
		print(3)
		res[v - 1] = 2
		res[u - 1] = 3
	else:
		print(2)
	for i in res:
		print(i, end=' ')
	print()


def main():
	T = int(input())
	for counter in range(T):
		(n, m) = map(int, input().split())
		indeg = [0 for i in range(n)]
		sum = 0
		u = 0
		v = 0
		for i in range(m):
			(u, v) = map(int, input().split())
			indeg[u - 1] += 1
			indeg[v - 1] += 1
			sum += 1
		cond = 0
		rank = [2 for i in range(n)]
		for i in range(n):
			if indeg[i] % 2 != 0 and cond == 0:
				index = i
				rank[i] = 1
				cond = 1
			if indeg[i] == 0:
				rank[i] = 1
		if m % 2 == 0:
			print('1')
			for i in range(n):
				print('1', end=' ')
			print('')
		elif cond == 0:
			print('3')
			rank[u - 1] = 3
			rank[v - 1] = 1
			for i in range(n):
				print(rank[i], end=' ')
			print('')
		else:
			print('2')
			for i in range(n):
				print(rank[i], end=' ')
			print('')
main()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
for _ in range(int(sys.stdin.readline())):
	(N, M) = get_ints()
	graph = [[] for i in range(N + 1)]
	all_even = 0
	for _ in range(M):
		(u, v) = get_ints()
		graph[u].append(v)
		graph[v].append(u)
		if len(graph[u]) % 2:
			all_even = all_even + 1
		else:
			all_even = all_even - 1
		if len(graph[v]) % 2:
			all_even = all_even + 1
		else:
			all_even = all_even - 1
	ans = ''
	if M % 2:
		if all_even == 0:
			sys.stdout.write('3\n')
			flag = False
			idx2 = -1
			for i in range(1, N + 1):
				if len(graph[i]) > 0 and (not flag):
					flag = True
					idx2 = graph[i][0]
					ans = ans + '1 '
				elif i == idx2:
					ans = ans + '2 '
				else:
					ans = ans + '3 '
		else:
			sys.stdout.write('2\n')
			flag = False
			for i in range(1, N + 1):
				if len(graph[i]) % 2 and (not flag):
					flag = True
					ans = ans + '2 '
				else:
					ans = ans + '1 '
	else:
		sys.stdout.write('1\n')
		for i in range(1, N + 1):
			ans = ans + '1 '
	ans = ans + '\n'
	sys.stdout.write(ans)


for _ in range(int(input())):
	(vertices, edges) = map(int, input().split())
	deg = [0] * (vertices + 1)
	for _ in range(edges):
		(v1, v2) = map(int, input().split())
		deg[v1] += 1
		deg[v2] += 1
	if edges % 2 == 0:
		print(1)
		ans = [1] * vertices
		print(*ans)
	else:
		oddv = 0
		ans = [1] * vertices
		for i in range(1, vertices + 1):
			if deg[i] % 2 != 0:
				oddv = i
				break
		if oddv > 0:
			print(2)
			ans[oddv - 1] = 2
			print(*ans)
		else:
			print(3)
			ans[v1 - 1] = 2
			ans[v2 - 1] = 3
			print(*ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	found = False
	d = {}
	for i in range(1, n + 1):
		d[i] = []
	for i in range(m):
		(x, y) = map(int, input().split())
		d[x].append(y)
		d[y].append(x)
	if m % 2 == 0:
		print(1)
		print(*[1] * n)
	else:
		l = [1] * n
		for i in d:
			if len(d[i]) % 2 == 1:
				l[i - 1] = 2
				found = True
				break
		if found:
			print(2)
			print(*l)
		else:
			print(3)
			for i in d:
				if len(d[i]) >= 1:
					(l[i - 1], l[d[i][0] - 1]) = (2, 3)
					print(*l)
					break


for _ in range(int(input())):
	g = {}
	(v, e) = map(int, input().split())
	degree = [0 for i in range(v + 1)]
	for i in range(e):
		(v1, v2) = map(int, input().split())
		degree[v1] += 1
		degree[v2] += 1
	if e % 2 == 0:
		print(1)
		for i in range(v):
			print('1', end=' ')
		print(' ')
	else:
		ov = 0
		for i in range(1, v + 1):
			if degree[i] % 2 != 0:
				ov = i
				break
		if ov > 0:
			print(2)
			for i in range(1, v + 1):
				if i == ov:
					print('2', end=' ')
				else:
					print('1', end=' ')
			print(' ')
		else:
			print(3)
			for i in range(1, v + 1):
				if i == v1:
					print('1', end=' ')
				elif i == v2:
					print('2', end=' ')
				else:
					print('3', end=' ')
			print(' ')


import math
import bisect
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter
INF = 10 ** 20
mod = 1000000007

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def process(Graph, N, M, v1, v2):
	if not M % 2:
		print(1)
		for i in range(N):
			print(1, end=' ')
		print()
	else:
		odd = 0
		for i in range(1, N + 1):
			if Graph[i] & 1:
				odd = i
				break
		if odd > 0:
			print(2)
			for i in range(1, N + 1):
				print(2 if i == odd else 1, end=' ')
			print()
		else:
			print(3)
			for i in range(1, N + 1):
				if i == v1:
					print(1, end=' ')
				elif i == v2:
					print(2, end=' ')
				else:
					print(3, end=' ')
			print()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		Graph = ddc(int)
		(v1, v2) = (0, 0)
		for i in range(M):
			(u, v) = map(int, input().split())
			Graph[u] += 1
			Graph[v] += 1
			(v1, v2) = (u, v)
		process(Graph, N, M, v1, v2)
main()


for _ in range(int(input())):
	graph = {}
	(v, e) = map(int, input().split())
	degree = [0] * (v + 1)
	for __ in range(e):
		(v1, v2) = map(int, input().split())
		degree[v1] += 1
		degree[v2] += 1
	if e & 1 == 0:
		print(1)
		for i in range(v):
			print('1', end=' ')
		print(' ')
	else:
		oddvertex = 0
		for i in range(1, v + 1):
			if degree[i] & 1:
				oddvertex = i
				break
		if oddvertex > 0:
			print(2)
			for i in range(1, v + 1):
				if i == oddvertex:
					print('2', end=' ')
				else:
					print('1', end=' ')
			print(' ')
		else:
			print(3)
			for i in range(1, v + 1):
				if i == v1:
					print('1', end=' ')
				elif i == v2:
					print('2', end=' ')
				else:
					print('3', end=' ')
			print(' ')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().strip().split())
	deg = [0] * n
	for x in range(m):
		(u, v) = map(int, input().strip().split())
		deg[u - 1] += 1
		deg[v - 1] += 1
	if m % 2 == 0:
		print(1)
		ans = [1] * n
		print(*ans)
	else:
		ans = [1] * n
		odd = -1
		for i in range(len(deg)):
			if deg[i] % 2 != 0:
				odd = i
				break
		if odd != -1:
			print(2)
			ans[odd] = 2
			print(*ans)
		else:
			print(3)
			ans[u - 1] = 2
			ans[v - 1] = 3
			print(*ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
for _ in range(inp()):
	(n, m) = mul()
	deg = [0] * n
	for x in range(m):
		(u, v) = mul()
		deg[u - 1] += 1
		deg[v - 1] += 1
	if m % 2 == 0:
		print(1)
		ans = [1] * n
		print(*ans)
	else:
		ans = [1] * n
		odd = -1
		for i in range(len(deg)):
			if deg[i] % 2 != 0:
				odd = i
				break
		if odd != -1:
			print(2)
			ans[odd] = 2
			print(*ans)
		else:
			print(3)
			ans[u - 1] = 2
			ans[v - 1] = 3
			print(*ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	g = {i + 1: [] for i in range(n)}
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	k = 1
	K = [1 for i in range(n)]
	if m % 2 == 0:
		print(k)
		print(*K)
		continue
	deg = [0] * n
	for i in range(n):
		deg[i] = len(g[i + 1])
	for i in range(n):
		if deg[i] % 2:
			K[i] = 2
			break
	else:
		K[u - 1] = 3
		K[v - 1] = 2
		print(k + 2)
		print(*K)
		continue
	print(k + 1)
	print(*K)


nums = int(input())
for q in range(nums):
	(n, m) = map(int, input().split())
	graph = [0 for i in range(n + 1)]
	ans = [1] * (n + 1)
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a] += 1
		graph[b] += 1
		x = a
		y = b
	if m % 2 == 0:
		print(1)
		print(*[1 for i in range(n)])
	else:
		for (i, val) in enumerate(graph[1:]):
			if val % 2 == 1:
				ans[i + 1] = 2
				print(2)
				print(*ans[1:])
				break
		else:
			ans[x] = 2
			ans[y] = 3
			print(3)
			print(*ans[1:])


for _ in range(int(input())):
	(v, e) = map(int, input().split())
	g = [0] * (v + 1)
	ans = [1] * (v + 1)
	for i in range(e):
		(a, b) = map(int, input().split())
		g[a] += 1
		g[b] += 1
		x = a
		y = b
	if not e & 1:
		print(1)
		print(*ans[1:])
		continue
	for (v, i) in enumerate(g[1:]):
		if i & 1:
			ans[v + 1] = 2
			print(2)
			print(*ans[1:])
			break
	else:
		ans[x] = 2
		ans[y] = 3
		print(3)
		print(*ans[1:])


tc = int(input())
for i in range(tc):
	(n, m) = map(int, input().split())
	deg = [0 for x in range(n + 1)]
	for j in range(m):
		(u, v) = map(int, input().split())
		deg[u] += 1
		deg[v] += 1
	if m % 2 == 0:
		print(1)
		arr = [1 for j in range(n)]
		print(*arr)
		continue
	else:
		degEven = True
		for j in range(n + 1):
			if deg[j] % 2 != 0:
				degEven = False
				other = j
				break
		if degEven:
			print(3)
			arr = [1 for j in range(n)]
			arr[u - 1] = 2
			arr[v - 1] = 3
			print(*arr)
		else:
			print(2)
			arr = [1 for j in range(n)]
			arr[other - 1] = 2
			print(*arr)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	sol = [0] * n
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		sol[u - 1] += 1
		sol[v - 1] += 1
	if m % 2 == 0:
		print(1)
		ans = [1] * n
		print(*ans)
	else:
		ans = [1] * n
		flag = -1
		for i in range(len(sol)):
			if sol[i] % 2 != 0:
				flag = i
				break
		if flag != -1:
			print(2)
			ans[flag] = 2
			print(*ans)
		else:
			print(3)
			ans[u - 1] = 2
			ans[v - 1] = 3
			print(*ans)


T = int(input())
ans = []
for _ in range(T):
	(N, M) = [int(i) for i in input().split()]
	D = [0 for i in range(N)]
	edges = []
	for i in range(M):
		(u, v) = [int(i) for i in input().split()]
		edges.append([u, v])
		D[u - 1] += 1
		D[v - 1] += 1
	if M % 2 == 0:
		K = 1
		s = '1 ' * N
		ans.append(K)
		ans.append(s.strip())
	else:
		odd = -1
		for i in range(N):
			if D[i] % 2 != 0:
				odd = i
				break
		if odd != -1:
			K = 2
			s = '1 ' * odd + '2 ' + '1 ' * (N - odd - 1)
			ans.append(K)
			ans.append(s.strip())
		else:
			K = 3
			e = edges[0]
			count = 2
			s = ''
			for i in range(N):
				if i == e[0] - 1 or i == e[1] - 1:
					s += str(count) + ' '
					count += 1
				else:
					s += '1 '
			ans.append(K)
			ans.append(s.strip())
for i in ans:
	print(i)


from collections import defaultdict

def solve(G, Num_Ver, Num_Edge):
	G1 = G
	ans = [1] * Num_Ver
	if Num_Edge % 2 == 0:
		return (1, ans)
	for i in range(N):
		if len(G[i]) % 2:
			ans[i] = 2
			return (2, ans)
	for i in range(N):
		if len(G[i]) != 0:
			ans[i] = 2
			ans[G1[i][0]] = 3
			return (3, ans)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	deg = [[] for _ in range(N)]
	for _ in range(M):
		(u, v) = map(int, input().split())
		deg[u - 1].append(v - 1)
		deg[v - 1].append(u - 1)
	ans1 = solve(deg, N, M)
	print(ans1[0])
	print(*ans1[1])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	deg = [0] * n
	for _ in range(m):
		(x, y) = map(int, input().split())
		deg[x - 1] += 1
		deg[y - 1] += 1
	if m % 2 == 0:
		print(1)
		ans = [1] * n
		print(*ans)
	else:
		ans = [1] * n
		flag = -1
		for i in range(len(deg)):
			if deg[i] % 2 != 0:
				flag = i
				break
		if flag != -1:
			ans[flag] = 2
			print(2)
			print(*ans)
		else:
			print(3)
			ans[x - 1] = 2
			ans[y - 1] = 3
			print(*ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(d, x, y, k, ans) = ({i: [] for i in range(1, n + 1)}, -1, -1, 1, [1 for i in range(n + 1)])
	for i in range(m):
		(x, y) = map(int, input().split())
		d[x].append(y)
		d[y].append(x)
	if m % 2 == 1:
		(k, isOdd) = (2, False)
		for i in range(1, n + 1):
			if len(d[i]) % 2 == 1:
				(ans[i], isOdd) = (2, True)
				break
		if not isOdd:
			(ans[x], ans[y], k) = (2, 3, 3)
	print(k)
	print(*ans[1:])


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	graph = []
	for i in range(n):
		graph.append([])
	for i in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		graph[x].append(y)
		graph[y].append(x)
	if m % 2 == 0:
		print(1)
		s = ''
		for i in range(1, n + 1):
			s += str(1) + ' '
		print(s)
	else:
		c = 0
		s = ''
		for i in range(n):
			if len(graph[i]) % 2 == 1:
				c = 1
				index = i
		if c:
			print(2)
			for i in range(n):
				if i == index:
					s += str(2) + ' '
				else:
					s += str(1) + ' '
			print(s)
		else:
			d = 0
			print(3)
			for i in range(n):
				if d == 0:
					if len(graph[i]) > 0:
						s += str(2) + ' '
						soap = graph[i][0]
						d = 1
					else:
						s += str(1) + ' '
				elif i == soap:
					s += str(3) + ' '
				else:
					s += str(1) + ' '
			print(s)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	deg = [int(0)] * (n + 1)
	for k in range(m):
		(u, v) = list(map(int, input().split()))
		deg[u] = 1 - deg[u]
		deg[v] = 1 - deg[v]
	if m % 2 == 0:
		print('1')
		for j in range(n):
			print('1', end=' ')
		print()
	elif max(deg) == 1:
		print('2')
		i = 1
		while i <= n:
			if deg[i] == 1:
				j = 1
				while j <= n:
					if j != i:
						print('1', end=' ')
					else:
						print('2', end=' ')
					j += 1
				print()
				break
			i += 1
	else:
		print('3')
		i = 1
		while i <= n:
			if i == u:
				print('1', end=' ')
			elif i == v:
				print('2', end=' ')
			else:
				print('3', end=' ')
			i += 1
		print()


from collections import defaultdict as dic
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = 0
	b = 0
	dick = dic(int)
	for i in range(m):
		(a, b) = map(int, input().split())
		dick[a] += 1
		dick[b] += 1
	if m % 2 == 0:
		print(1)
		for i in range(1, n + 1):
			print(1, end=' ')
	else:
		even = True
		ans = 0
		for i in dick:
			if dick[i] % 2 == 1:
				even = False
				ans = i
		if not even:
			print(2)
			for i in range(1, n + 1):
				if i != ans:
					print(1, end=' ')
				else:
					print(2, end=' ')
		else:
			print(3)
			for i in range(1, n + 1):
				if i != a and i != b:
					print(1, end=' ')
				elif i == a:
					print(2, end=' ')
				else:
					print(3, end=' ')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = [[] for __ in range(n)]
	l = [0] * n
	r = [1] * n
	for __ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
		l[u] += 1
		l[v] += 1
	d = 1
	if not m % 2:
		print(1)
		print(*r)
	else:
		for i in range(n):
			if l[i] % 2 and l[i] != 0:
				d = 2
				r[i] = 2
				break
		else:
			for i in range(n):
				if l[i]:
					d = 3
					r[i] = 2
					r[g[i][0]] = 3
					break
		print(d)
		print(*r)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split(' '))
	f = 0
	l = [0] * n
	res = [1] * n
	for i in range(m):
		(u, v) = map(int, input().split(' '))
		l[u - 1] = l[u - 1] + 1
		l[v - 1] = l[v - 1] + 1
	if m % 2 == 0:
		print(1)
	else:
		for i in range(n):
			if l[i] % 2 == 1:
				res[i] = 2
				f = 1
				print(2)
				break
		if f == 0:
			res[u - 1] = 2
			res[v - 1] = 3
			print(3)
	for i in res:
		print(i, end=' ')
	print()
	t = t - 1


import sys
sys.setrecursionlimit(100000)
visited = []

def number_of_components(adj, x):
	visited[x] = 1
	edge = len(adj[x])
	for i in adj[x]:
		if visited[i] == 0:
			edge += number_of_components(adj, i)
	return edge
t = int(input())
while t > 0:
	data = []
	(n, m) = map(int, input().split())
	for i in range(m):
		(x, y) = map(int, input().split())
		data.append(x)
		data.append(y)
	adj = [[] for k in range(n)]
	degree = [0] * n
	visited = [0] * n
	mark = []
	flag = 0
	if m % 2 == 0:
		mark = [1] * n
		print('1')
		for k in mark:
			print(k, end=' ')
	else:
		for i in range(0, len(data) - 1, 2):
			adj[data[i] - 1].append(data[i + 1] - 1)
			adj[data[i + 1] - 1].append(data[i] - 1)
			degree[data[i] - 1] += 1
			degree[data[i + 1] - 1] += 1
		for i in range(n):
			if degree[i] % 2 != 0:
				odd = i
				flag = 1
				break
		mark = [1] * n
		if flag == 1:
			mark[odd] = 2
			print('2')
			for j in mark:
				print(j, end=' ')
		else:
			for i in range(n):
				if visited[i] == 0:
					deg = number_of_components(adj, i)
					ed = deg // 2
					if ed % 2 != 0:
						mark[i] = 2
						nex = adj[i][0]
						mark[nex] = 3
						break
			print('3')
			for j in mark:
				print(j, end=' ')
		print()
	t -= 1


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	G = {}
	deg = [0] * (N + 1)
	for i in range(1, N + 1):
		G[i] = []
	for _ in range(M):
		(u, v) = list(map(int, sys.stdin.readline().split()))
		deg[u] += 1
		deg[v] += 1
		G[u].append(v)
		G[v].append(u)
	if M % 2 == 0:
		print(1)
		for i in range(1, N + 1):
			print(1, end=' ')
	else:
		x = -1
		for i in range(1, N + 1):
			if deg[i] % 2 != 0:
				x = i
				break
		if x != -1:
			print(2)
			for i in range(1, N + 1):
				if i != x:
					print(1, end=' ')
				else:
					print(2, end=' ')
		else:
			print(3)
			x = -1
			for i in range(1, N + 1):
				if deg[i] >= 2:
					x = i
					break
			y = G[x][0]
			for i in range(1, N + 1):
				if i == x:
					print(2, end=' ')
				elif i == y:
					print(3, end=' ')
				else:
					print(1, end=' ')
	print()


import bisect
from collections import defaultdict
test = int(input())

class Graph:

	def __init__(self, v):
		self.v = v
		self.graph = defaultdict(list)
		self.d = {}

	def addedge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)
		if u in self.d:
			self.d[u] += 1
		else:
			self.d[u] = 1
		if v in self.d:
			self.d[v] += 1
		else:
			self.d[v] = 1

	def removeedge(self, x):
		a = self.graph[x]
		del self.graph[x]
		for i in range(len(a)):
			self.d[a[i]] -= 1
while test > 0:
	test -= 1
	(n, m) = map(int, input().split())
	g = Graph(n)
	result = [1 for i in range(n + 1)]
	flag = 0
	m1 = m
	max1 = 0
	while m > 0:
		m -= 1
		(u, v) = map(int, input().split())
		g.addedge(u, v)
	if m1 % 2 == 0:
		flag = 1
		max1 = 1
	else:
		for i in g.d:
			if g.d[i] % 2 != 0:
				flag = 1
				result[i] = 2
				break
		for i in range(1, n + 1):
			if i not in g.d:
				result[i] = 2
		max1 = 2
	if flag == 0:
		a = 0
		fl1 = 0
		for i in g.d:
			g.removeedge(i)
			a = i
			break
		for i in g.d:
			if g.d[i] % 2 != 0 and result[i] == 1:
				fl1 = 1
				result[i] = 2
				break
		if fl1 == 1:
			max1 = 3
			result[a] = 3
		else:
			max1 = 2
			result[a] = 2
	print(max1)
	for i in range(1, len(result)):
		print(result[i], end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	d = [0] * (n + 1)
	for _ in range(m):
		(u, v) = list(map(int, input().split()))
		d[u] += 1
		d[v] += 1
	u_ = u
	v_ = v
	if m % 2 == 0:
		print('1')
		print(' '.join(['1'] * n))
		continue
	for u in range(1, n + 1):
		if d[u] % 2 == 1:
			print('2')
			ans = ['1'] * (u - 1) + ['2'] + ['1'] * (n - u)
			print(' '.join(ans))
			break
	else:
		print('3')
		ans = ['3' if i == u_ else '2' if i == v_ else '1' for i in range(1, n + 1)]
		print(' '.join(ans))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ds = {}
	for _ in range(m):
		(u, v) = map(int, input().split())
		e = (u, v)
		ds[u] = ds.get(u, 0) + 1
		ds[v] = ds.get(v, 0) + 1
	if m % 2 == 0:
		print(1)
		print(' '.join(['1'] * n))
	else:
		v = next((v for v in ds if ds[v] % 2 == 1), None)
		if v:
			print(2)
			t = {v: '2'}
			print(' '.join([t.get(i, '1') for i in range(1, n + 1)]))
		else:
			print(3)
			t = {e[0]: '2', e[1]: '3'}
			print(' '.join([t.get(i, '1') for i in range(1, n + 1)]))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(m):
		(u, v) = map(int, input().split())
		try:
			d[u].append(v)
		except:
			d[u] = [v]
		try:
			d[v].append(u)
		except:
			d[v] = [u]
	l = [1] * n
	if m % 2 == 0:
		print(1)
		print(*l)
	else:
		f = True
		for (i, j) in d.items():
			if len(j) % 2 != 0:
				l[i - 1] = 2
				f = False
				break
		if f == False:
			print(2)
			print(*l)
		else:
			c = 1
			for (i, j) in d.items():
				if c == 3:
					break
				elif len(j) % 2 == 0:
					l[i - 1] += c
					c += 1
			print(3)
			print(*l)


for _ in range(int(input())):
	(ver, edge) = map(int, input().split())
	degree = {}
	for i in range(edge):
		(v1, v2) = map(int, input().split())
		if v1 not in degree.keys():
			degree[v1] = [v2]
		else:
			degree[v1].append(v2)
		if v2 not in degree.keys():
			degree[v2] = [v1]
		else:
			degree[v2].append(v1)
	ans = [1] * ver
	if edge % 2 == 0:
		print(1)
		print(*ans)
	else:
		even = True
		for (key, values) in degree.items():
			if len(values) % 2 != 0:
				ans[key - 1] += 1
				even = False
				break
		if even == False:
			print(2)
			print(*ans)
		else:
			k = 1
			for (key, values) in degree.items():
				if len(values) % 2 == 0:
					ans[key - 1] += k
					k += 1
				if k == 3:
					break
			print(3)
			print(*ans)


from sys import stdin
from collections import defaultdict
t = int(stdin.readline())
while t:
	(n, m) = [int(x) for x in stdin.readline().split()]
	vertices_deg = defaultdict(int)
	(adj_1, adj_2) = (0, 0)
	for i in range(m):
		(u, v) = [int(x) for x in stdin.readline().split()]
		vertices_deg[u] += 1
		vertices_deg[v] += 1
		(adj_1, adj_2) = (u, v)
	if m % 2 == 0:
		print(1)
		for i in range(n):
			print(1, end=' ')
	else:
		temp = 0
		flag = 0
		for i in range(1, n + 1):
			if vertices_deg[i] % 2 != 0:
				temp = i
				flag = 1
				break
		if flag == 1:
			print(2)
			for i in range(1, n + 1):
				if i == temp:
					print(2, end=' ')
				else:
					print(1, end=' ')
		else:
			print(3)
			for i in range(1, n + 1):
				if i == adj_1:
					print(3, end=' ')
				elif i == adj_2:
					print(2, end=' ')
				else:
					print(1, end=' ')
	t -= 1


for case in range(int(input())):
	(vertices, edges) = [int(x) for x in input().split()]
	dependecies = {}
	edges_dict = {}
	new_vertices = ['1'] * vertices
	for i in range(vertices):
		dependecies[i] = 0
		edges_dict[i] = []
	for edge in range(edges):
		(u, v) = [int(x) - 1 for x in input().split()]
		dependecies[u] += 1
		dependecies[v] += 1
		edges_dict[u].append(v)
		edges_dict[v].append(u)
	if edges % 2 == 0:
		print(1)
		print('1 ' * vertices)
		continue
	else:
		odd_dependency_vertex = -1
		for vertex in dependecies.keys():
			if dependecies[vertex] % 2 != 0:
				odd_dependency_vertex = vertex
				break
		if odd_dependency_vertex != -1:
			new_vertices[odd_dependency_vertex] = '2'
			print(2)
			print(' '.join(new_vertices))
		else:
			first = -1
			for i in range(vertices):
				if dependecies[i] == 0:
					pass
				elif first == -1:
					first = i
					break
			second = edges_dict[first][0]
			print(3)
			new_vertices[first] = '2'
			new_vertices[second] = '3'
			print(' '.join(new_vertices))


test = int(input())
for testcase in range(test):
	a = {}
	c = {}
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	for i in range(m):
		(x, y) = input().split(' ')
		x = int(x)
		y = int(y)
		if x in a:
			a[x].append(y)
		else:
			a[x] = [y]
		if y in a:
			a[y].append(x)
		else:
			a[y] = [x]
	for i in range(1, n + 1):
		c[i] = 0
	if m % 2 == 0:
		print(1)
		for i in range(n):
			print(1, end=' ')
	else:
		even_check = mark = odd_check = zero_check = 0
		for i in a:
			c[i] = len(a[i])
			if c[i] % 2 == 0 and c[i] != 0:
				even_check += 1
			elif c[i] == 0:
				zero_check += 1
			else:
				odd_check += 1
			mark += 1
		if even_check + zero_check == mark:
			print(3)
			temp1 = n + 1
			for i in c:
				if c[i] != 0:
					temp1 = i
			if temp1 != n + 1:
				temp2 = a[temp1][0]
				for i in range(1, n + 1):
					if i == temp1:
						print(2, end=' ')
					elif i == temp2:
						print(3, end=' ')
					else:
						print(1, end=' ')
		else:
			temp = n
			for i in c:
				if c[i] % 2 != 0:
					if c[i] < temp:
						temp = i
			if odd_check == 2:
				if zero_check == mark - 2:
					print(2)
					for i in range(1, n + 1):
						if i != temp:
							print(1, end=' ')
						else:
							print(2, end=' ')
				else:
					print(2)
					for i in range(1, n + 1):
						if i != temp:
							print(1, end=' ')
						else:
							print(2, end=' ')
			else:
				print(2)
				for i in range(1, n + 1):
					if i != temp:
						print(1, end=' ')
					else:
						print(2, end=' ')


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	E = [set() for _ in range(N)]
	D = [0 for _ in range(N)]
	A = 0
	for _ in range(M):
		(u, v) = map(int, input().split())
		E[u - 1].add(v - 1)
		E[v - 1].add(u - 1)
	odd_edge = []
	for i in range(N):
		D[i] = len(E[i])
		A += D[i]
		if D[i] & 1:
			odd_edge.append(i)
	if not A // 2 & 1:
		print(1)
		print(*[1 for _ in range(N)])
		continue
	P = []
	if len(odd_edge):
		P.append({odd_edge[0]: 1})
		P2 = {}
		for i in range(N):
			if i != odd_edge[0]:
				P2[i] = 2
		P.append(P2)
	else:
		v = None
		for i in range(N):
			if len(E[i]) > 0:
				(x, y) = (i, E[i].pop())
				P.append({x: 1})
				P.append({y: 2})
				break
		P3 = {}
		for i in range(N):
			if i != x and i != y:
				P3[i] = 3
		P.append(P3)
	print(len(P))
	for i in range(N):
		for (p, j) in enumerate(P):
			if i in j:
				print(p + 1, end=' ')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	degree = [0] * n
	for i in range(m):
		(u, v) = map(int, input().split())
		degree[u - 1] += 1
		degree[v - 1] += 1
	ans = 0
	if m % 2 == 0:
		ans = 1
	else:
		flag = 0
		for i in range(n):
			if degree[i] % 2 != 0:
				flag = 1
				temp = i
				break
		if flag == 1:
			ans = 2
		else:
			ans = 3
	if ans == 1:
		print(1)
		print('1 ' * n)
	elif ans == 2:
		print(2)
		for i in range(n):
			if i == temp:
				print('2', end=' ')
			else:
				print('1', end=' ')
		print()
	else:
		print(3)
		for i in range(n):
			if i == u - 1:
				print(2, end=' ')
			elif i == v - 1:
				print(3, end=' ')
			else:
				print(1, end=' ')
		print()


t = int(input())
for i in range(t):
	for j11 in range(500):
		pass
	(n, m) = map(int, input().split())
	a = [0 for i in range(n)]
	dic = {}
	count = 0
	for i in range(m):
		(x, y) = map(int, input().split())
		a[x - 1] += 1
		a[y - 1] += 1
		if x - 1 in dic:
			dic[x - 1].append(y - 1)
		else:
			dic[x - 1] = [y - 1]
			count += 1
		if y - 1 in dic:
			dic[y - 1].append(x - 1)
		else:
			dic[y - 1] = [x - 1]
			count += 1
	for i in range(n):
		if i in dic:
			pass
		else:
			dic[i] = []
	if m % 2 == 0:
		print('1')
		b = [1 for i in range(n)]
		print(*b)
	else:
		b = []
		k = 2
		flag = 0
		for i in a:
			if i % 2 != 0 and flag == 0:
				b.append(k)
				flag = 1
			else:
				b.append(1)
		if flag == 0:
			for i in range(n):
				if len(dic[i]) % 2 == 0 and len(dic[i]) > 1:
					b[i] = k
					k += 1
					break
			b[dic[i][0]] = k
		print(k)
		print(*b)


t = int(input())
for q in range(t):
	(n, m) = map(int, input().split())
	l = [0] * n
	for i in range(m):
		(x, y) = map(int, input().split())
		l[x - 1] += 1
		l[y - 1] += 1
	ans = [1] * n
	if m & 1 == 1:
		f = 0
		for i in range(n):
			if l[i] & 1 == 1:
				ans[i] = 2
				f = 1
				break
		if f == 1:
			print(2)
		else:
			print(3)
			ans[x - 1] = 2
			ans[y - 1] = 3
	else:
		print(1)
	print(*ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = [int(a) for a in input().split()]
	graph = defaultdict(list)
	new_graph = [1] * n
	for i in range(m):
		(u, v) = [int(a) for a in input().split()]
		graph[u].append(v)
		graph[v].append(u)
	if m % 2 == 0:
		print(1)
		print(*new_graph)
	else:
		for i in graph:
			if len(graph[i]) % 2 != 0:
				new_graph[i - 1] += 1
				print(2)
				print(*new_graph)
				break
		else:
			cnt = 1
			for i in graph:
				if len(graph[i]) % 2 == 0:
					new_graph[i - 1] += cnt
					cnt += 1
				if cnt == 3:
					break
			print(3)
			print(*new_graph)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ed = [0] * (n + 1)
	sol = ['1'] * n
	edge = []
	tot = 0
	for i in range(m):
		(x, y) = map(int, input().split())
		edge.append((x, y))
		ed[x] += 1
		ed[y] += 1
		tot += 1
	if tot % 2 == 0:
		print(1)
		res = ' '.join(sol)
		print(res)
	else:
		for i in range(1, n + 1):
			if ed[i] % 2 != 0:
				sol[i - 1] = '2'
				break
		else:
			temp1 = edge.pop()
			sol[temp1[0] - 1] = '2'
			sol[temp1[1] - 1] = '3'
			print(3)
			res = ' '.join(sol)
			print(res)
			continue
		print(2)
		res = ' '.join(sol)
		print(res)


for step in range(int(input())):
	(n, m) = map(int, input().split())
	A = [0] * (n + 1)
	for i in range(m - 1):
		(u, v) = map(int, input().split())
		A[u] += 1
		A[v] += 1
	(u, v) = map(int, input().split())
	A[u] += 1
	A[v] += 1
	if m % 2 == 0:
		print(1)
		Ans = ''
		for i in range(1, len(A)):
			Ans += '1 '
		print(Ans)
	if m % 2 != 0:
		flag = 0
		for i in range(len(A)):
			if A[i] % 2 != 0:
				flag = 1
				j = i
				break
		if flag == 1:
			print(2)
			Ans = ''
			for i in range(1, len(A)):
				if i == j:
					Ans += '2 '
				else:
					Ans += '1 '
			print(Ans)
		if flag == 0:
			print(3)
			Ans = ''
			for i in range(1, len(A)):
				if i == u:
					Ans += '2 '
				elif i == v:
					Ans += '3 '
				else:
					Ans += '1 '
			print(Ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	degree = [[] for i in range(n + 1)]
	res = [1 for i in range(n + 1)]
	for __ in range(m):
		(u, v) = map(int, input().split())
		degree[u].append(v)
		degree[v].append(u)
	if m % 2 != 0:
		oddNode = -1
		for i in range(1, n + 1):
			if len(degree[i]) % 2 != 0:
				print(2)
				oddNode = i
				res[i] = 2
				break
		if oddNode == -1:
			print(3)
			for i in range(1, n + 1):
				if len(degree[i]) > 0:
					res[i] = 2
					res[degree[i][0]] = 3
					break
	else:
		print(1)
	for i in range(1, n + 1):
		print(res[i], end=' ')
	print()


for T in range(int(input())):
	(vert, edges) = map(int, input().split())
	degrees = {}
	for i in range(edges):
		(v1, v2) = map(int, input().split())
		if v1 in degrees.keys():
			degrees[v1].append(v2)
		else:
			degrees[v1] = [v2]
		if v2 in degrees.keys():
			degrees[v2].append(v1)
		else:
			degrees[v2] = [v1]
	subGraphs = [1] * vert
	if edges % 2 == 0:
		print(1)
		print(*subGraphs)
	else:
		even = True
		for (key, values) in degrees.items():
			if len(values) % 2 != 0:
				subGraphs[key - 1] += 1
				even = False
				break
		if even == False:
			print(2)
			print(*subGraphs)
		else:
			cnt = 1
			for (key, values) in degrees.items():
				if len(values) % 2 == 0:
					subGraphs[key - 1] += cnt
					cnt += 1
				if cnt == 3:
					break
			print(3)
			print(*subGraphs)


rr = lambda : input().strip()
rri = lambda : int(rr())
rrm = lambda : [int(x) for x in rr().split()]

def sol(n, m):
	graph = dict()
	for i in range(m):
		(x, y) = rrm()
		if x in graph:
			graph[x].append(y)
		else:
			graph[x] = [y]
		if y in graph:
			graph[y].append(x)
		else:
			graph[y] = [x]
	if m % 2 == 0:
		print(1)
		res = ''
		for i in range(n):
			res += '1 '
		print(res[:-1])
	else:
		ev = True
		for e in graph:
			if len(graph[e]) % 2 != 0:
				x = e
				ev = False
				break
		if ev:
			keys = list(graph.keys())
			x = keys[0]
			y = graph[x][0]
			print(3)
			res = ''
			for i in range(1, n + 1):
				if i == x:
					res += '2 '
				elif i == y:
					res += '3 '
				else:
					res += '1 '
			print(res[:-1])
		else:
			print(2)
			res = ''
			for i in range(1, n + 1):
				if i == x:
					res += '2 '
				else:
					res += '1 '
			print(res[:-1])
T = rri()
for _ in range(T):
	(n, m) = rrm()
	ans = sol(n, m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [0] * n
	connect = []
	arr1 = []
	z = -1
	for i in range(m):
		(aa, bb) = map(int, input().split())
		arr[aa - 1] += 1
		arr[bb - 1] += 1
		x = aa - 1
		y = bb - 1
	if m % 2 == 0:
		print(1)
		print(*[1] * n)
	else:
		for i in arr:
			if i % 2 != 0:
				z = arr.index(i)
				break
		if z != -1:
			print(2)
			for i in range(n):
				arr1.append(1)
			arr1[z] = 2
			print(*arr1)
		else:
			print(3)
			res = [3] * n
			res[x] = 1
			res[y] = 2
			print(*res)


t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	indeg = [0 for i in range(n)]
	for i in range(m):
		(u, v) = [int(i) for i in input().split()]
		indeg[u - 1] += 1
		indeg[v - 1] += 1
	if m % 2 == 0:
		print(1)
		out = '1'
		for i in range(n - 1):
			out = out + ' 1'
		print(out)
	else:
		loop = 1
		for i in range(n):
			if indeg[i] % 2 == 1:
				loop = 0
				break
		if loop == 0:
			print(2)
			for i in range(n):
				if indeg[i] % 2 == 1:
					sec = i
					break
			if sec == 0:
				out = '2'
				for i in range(n - 1):
					out = out + ' 1'
				print(out)
			else:
				out = '1'
				for i in range(1, sec):
					out = out + ' 1'
				out = out + ' 2'
				for i in range(sec + 1, n):
					out = out + ' 1'
				print(out)
		else:
			print(3)
			printtt = [1 for i in range(n)]
			printtt[u - 1] = 2
			printtt[v - 1] = 3
			out = str(printtt[0])
			for i in range(1, n):
				out = out + ' ' + str(printtt[i])
			print(out)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	arr = {}
	for i in range(m):
		(u, v) = map(int, input().split())
		if u in arr.keys():
			arr[u].append(v)
		else:
			arr[u] = [v]
		if v in arr.keys():
			arr[v].append(u)
		else:
			arr[v] = [u]
	ans = [1] * n
	if m % 2 == 0:
		print(1)
		print(*ans)
	else:
		f = True
		for (key, values) in arr.items():
			if len(values) % 2 != 0:
				ans[key - 1] += 1
				f = False
				break
		if f == False:
			print(2)
			print(*ans)
		else:
			count = 1
			for (key, values) in arr.items():
				if count == 3:
					break
				if len(values) % 2 == 0:
					ans[key - 1] += count
					count += 1
			print(3)
			print(*ans)


test = int(input())
for i in range(test):
	(num1, num2) = map(int, input().split())
	arr = [0] * num1
	connect = []
	arr1 = []
	z = -1
	for i in range(num2):
		(q, r) = map(int, input().split())
		arr[q - 1] += 1
		arr[r - 1] += 1
		x = q - 1
		y = r - 1
	if num2 % 2 == 0:
		print(1)
		print(*[1] * num1)
	else:
		for i in arr:
			if i % 2 != 0:
				z = arr.index(i)
				break
		if z != -1:
			print(2)
			for i in range(num1):
				arr1.append(1)
			arr1[z] = 2
			print(*arr1)
		else:
			print(3)
			res = [3] * num1
			res[x] = 1
			res[y] = 2
			print(*res)


Total_number_of_testcases = input()
Total_number_of_testcases = int(Total_number_of_testcases)
for a_testcase in range(Total_number_of_testcases):
	specified_input = input().split()
	track_of_edges = {}
	for items in specified_input:
		specified_input_1 = int(specified_input[0])
		specified_input_2 = int(specified_input[1])
	for specifier in range(specified_input_2):
		specified_input = input().split()
		for items in specified_input:
			specified_input_3 = int(specified_input[0])
			specified_input_4 = int(specified_input[1])
		if track_of_edges.get(specified_input_3) != None:
			track_of_edges[specified_input_3][0] += 1
			track_of_edges[specified_input_3].append(specified_input_4)
		elif track_of_edges.get(specified_input_3) == None:
			track_of_edges[specified_input_3] = [1, specified_input_4]
		else:
			pass
		if track_of_edges.get(specified_input_4) == None:
			track_of_edges[specified_input_4] = [1, specified_input_3]
		elif track_of_edges.get(specified_input_4) != None:
			track_of_edges[specified_input_4][0] += 1
			track_of_edges[specified_input_4].append(specified_input_3)
		else:
			pass
	intermediate = True
	for index_element in track_of_edges.keys():
		if track_of_edges[index_element][0] % 2 == 1:
			intermediate = False
		else:
			pass
	if specified_input_2 % 2 == 1:
		if intermediate == True:
			print(3)
			tracker_element = 1
			while track_of_edges.get(tracker_element) == None:
				print(1, end=' ')
				tracker_element += 1
			specified_input_2 -= track_of_edges[tracker_element][0]
			for check_element in range(1, len(track_of_edges[tracker_element])):
				track_of_edges[track_of_edges[tracker_element][check_element]][0] -= 1
			print(1, end=' ')
			tracker_element = tracker_element + 1
			track_element = True
			for element_in_tracker in range(tracker_element, specified_input_1 + 1):
				if track_of_edges.get(element_in_tracker) == None:
					print(1, end=' ')
				elif (specified_input_2 - track_of_edges[element_in_tracker][0]) % 2 == 0:
					if track_element:
						print(2, end=' ')
						track_element = False
					else:
						print(3, end=' ')
				else:
					print(3, end=' ')
		else:
			print(2)
			track_element_1 = True
			for element_in_specified in range(1, specified_input_1 + 1):
				if track_of_edges.get(element_in_specified) == None:
					print(2, end=' ')
				elif track_of_edges[element_in_specified][0] % 2 == 0:
					print(1, end=' ')
				elif track_element_1:
					print(2, end=' ')
					track_element_1 = False
				else:
					print(1, end=' ')
	else:
		print(1)
		for iterator in range(1, specified_input_1 + 1):
			print(1, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().strip().split())
	l = [[0] for j in range(n + 1)]
	for j in range(m):
		a = list(map(int, input().strip().split()))
		l[a[0]].append(a[1])
		l[a[1]].append(a[0])
	if m % 2 == 0:
		ans = [1 for k in range(n)]
		print(1)
		print(*ans)
	else:
		p = 0
		for k in range(1, n + 1):
			if (len(l[k]) - 1) % 2 != 0:
				p = k
				break
		if p > 0:
			print(2)
			hh = []
			for qw in range(1, n + 1):
				if qw == p:
					hh.append(2)
				else:
					hh.append(1)
			print(*hh)
		else:
			q = 0
			print(3)
			for qa in range(1, n + 1):
				if len(l[qa]) >= 2:
					p = qa
					q = l[qa][1]
					break
			hh1 = []
			for po in range(1, n + 1):
				if po == p:
					hh1.append(2)
				elif po == q:
					hh1.append(3)
				else:
					hh1.append(1)
			print(*hh1)


T = int(input())
while T:
	T -= 1
	u = 0
	v = 0
	(n, m) = [int(i) for i in input().split()]
	a = [0] * (n + 1)
	for i in range(m):
		(u, v) = [int(i) for i in input().split()]
		a[u] += 1
		a[v] += 1
	if m & 1:
		b = 0
		val = -1
		for i in range(n):
			if a[i + 1] & 1:
				b = 1
				val = i
				break
		if b:
			print(2)
			for i in range(n):
				if i == val:
					print(2, end=' ')
				else:
					print(1, end=' ')
			print()
		else:
			print(3)
			for i in range(n):
				if i == u - 1:
					print(2, end=' ')
				elif i == v - 1:
					print(3, end=' ')
				else:
					print(1, end=' ')
			print()
	else:
		print(1)
		for i in range(n):
			print(1, end=' ')
		print()


try:
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		m = 1
		A = []
		B = []
		for i in range(0, N + 1):
			A.append(0)
			B.append(1)
		(u, v) = map(int, input().split())
		X = u
		Y = v
		A[u] += 1
		A[v] += 1
		for i in range(2, M + 1):
			(u, v) = map(int, input().split())
			A[u] += 1
			A[v] += 1
		if M % 2 != 0:
			f = 0
			g = 0
			for i in range(1, N + 1):
				if A[i] != 0:
					if A[i] % 2 != 0:
						f += 1
						g = i
						break
			if f > 0:
				B[g] = 2
				m = 2
			else:
				B[X] = 2
				B[Y] = 3
				m = 3
		print(m)
		for i in range(1, N + 1):
			print(B[i], end=' ')
except:
	pass


t = int(input())
for o in range(t):
	(nodes, edges) = list(map(int, input().split()))
	degree = [0] * (nodes + 1)
	graph = {}
	for i in range(1, nodes + 1):
		graph[i] = []
	edgs = 0
	temp1 = -1
	temp2 = -1
	for i in range(edges):
		(x, y) = list(map(int, input().split()))
		if y in graph[x]:
			continue
		edgs = edgs + 1
		temp1 = x
		temp2 = y
		degree[x] = degree[x] + 1
		degree[y] = degree[y] + 1
		graph[x].append(y)
		graph[y].append(x)
	if edgs % 2 == 0:
		print(1)
		print(*[1] * nodes)
		continue
	even = 0
	odd = 0
	oddarr = []
	evenarr = []
	ans = [1] * (nodes + 1)
	for i in range(1, nodes + 1):
		if degree[i] == 0:
			continue
		if degree[i] % 2 == 0:
			even = even + 1
			evenarr.append(i)
		else:
			odd = odd + 1
			oddarr.append(i)
	if odd == 0:
		print(3)
		ans[temp1] = 2
		ans[temp2] = 3
	else:
		print(2)
		ans[oddarr[0]] = 2
	print(*ans[1:])


import itertools as itt
from sys import stdin, stdout
from functools import reduce
from collections import Counter as co
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	arr = [0] * N
	ex = 0
	ey = 0
	for i in range(M):
		(x, y) = map(int, input().split())
		arr[x - 1] += 1
		arr[y - 1] += 1
		ex = x - 1
		ey = y - 1
	if M % 2 == 0:
		print('1')
		for i in range(N):
			print('1 ', end='')
		print()
	else:
		flag = -1
		for i in range(N):
			if arr[i] % 2 != 0:
				flag = i
				break
		if flag != -1:
			print('2')
			for i in range(N):
				if i == flag:
					print('2 ', end='')
				else:
					print('1 ', end='')
			print()
		else:
			print('3')
			for i in range(N):
				if i == ex:
					print('2 ', end='')
				elif i == ey:
					print('3 ', end='')
				else:
					print('1 ', end='')
			print()


for k in range(int(input())):
	(n, M) = map(int, input().split())
	arr = [0] * n
	arr1 = []
	z = -1111
	for i in range(M):
		(U, V) = map(int, input().split())
		y = V - 1
		x = U - 1
		arr[V - 1] += 1
		arr[U - 1] += 1
	if M % 2 == 0:
		print(1)
		print(*[1] * n)
	else:
		for i in arr:
			if i % 2 != 0:
				z = arr.index(i)
				break
		if z != -1111:
			print(2)
			for i in range(n):
				arr1.append(1)
			arr1[z] = 2
			print(*arr1)
		else:
			print(3)
			result = [3] * n
			result[x] = 1
			result[y] = 2
			print(*result)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	rl = []
	cl = []
	rl1 = []
	cl1 = []
	hl = [0] * n
	for i in range(0, m):
		(x, y) = map(int, input().split())
		hl[x - 1] = hl[x - 1] + 1
		hl[y - 1] = hl[y - 1] + 1
		hh1 = x
		hh2 = y
	if m % 2 == 0:
		print('1')
		for i in range(0, n):
			print('1 ', end='')
		print()
	else:
		for nn in hl:
			if nn % 2 == 0:
				flag = 3
			else:
				flag = 2
				break
		if flag == 2:
			print('2')
			oddflag = 0
			for jj in hl:
				if jj % 2 != 0 and oddflag == 0:
					print('2 ', end='')
					oddflag = 1
				elif jj == 0:
					print('2 ', end='')
				else:
					print('1 ', end='')
			print()
		else:
			print('3')
			for jj in range(0, n):
				if jj + 1 == hh1:
					print('2 ', end='')
				elif jj + 1 == hh2:
					print('3 ', end='')
				else:
					print('1 ', end='')
			print()
	t = t - 1


t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	li = [[] for i in range(n + 1)]
	for i in range(0, m):
		(k, l) = [int(x) for x in input().split()]
		li[k].append(l)
		li[l].append(k)
	if m % 2 == 0:
		print(1)
		for i in range(1, n + 1):
			print(1, end=' ')
	else:
		mini1 = 1000000000000
		mini2 = 1000000000000
		k1 = 0
		k2 = 0
		for i in range(1, n + 1):
			if len(li[i]) % 2 != 0 and len(li[i]) < mini1:
				k1 = i
				mini1 = len(li[i])
			elif len(li[i]) % 2 == 0 and len(li[i]) < mini2 and (len(li[i]) > 0):
				k2 = i
				mini2 = len(li[i])
		if mini1 != 1000000000000:
			print(2)
			for i in range(1, n + 1):
				if i == k1:
					print(1, end=' ')
				else:
					print(2, end=' ')
		else:
			print(3)
			for i in range(1, n + 1):
				if i == k2:
					print(2, end=' ')
				elif i == li[k2][0]:
					print(1, end=' ')
				else:
					print(3, end=' ')
	t = t - 1


t = int(input())
for _ in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	sol = [1] * n
	if m % 2 == 0:
		for _ in range(m):
			(u, v) = input().split()
		print(1)
		print(*sol)
	else:
		graph = dict()
		edges = set()
		for _ in range(m):
			(u, v) = input().split()
			u = int(u)
			v = int(v)
			if u in edges:
				edges.remove(u)
			else:
				edges.add(u)
			if v in edges:
				edges.remove(v)
			else:
				edges.add(v)
			if u in graph:
				graph[u].add(v)
			else:
				graph[u] = set([v])
			if v in graph:
				graph[v].add(u)
			else:
				graph[v] = set([u])
		if len(edges) != 0:
			print(2)
			sol[edges.pop() - 1] = 2
			print(*sol)
		else:
			all_keys = list(graph.keys())
			k1 = all_keys[0]
			sol[k1 - 1] = 3
			k2 = list(graph[k1])
			sol[k2[0] - 1] = 2
			print(3)
			print(*sol)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(m):
		(u, v) = map(int, input().split())
		U = u
		V = v
		arr.append(u)
		arr.append(v)
	di = {}
	for i in range(len(arr)):
		if arr[i] in di.keys():
			di[arr[i]] = di[arr[i]] + 1
		else:
			di[arr[i]] = 1
	if m % 2 == 0:
		print(1)
		for i in range(1, n + 1):
			print(1, end=' ')
		print('')
	else:
		count = count2 = cof2 = 0
		for item in di.items():
			if item[1] % 2 == 0:
				count = count + 1
			count2 = count2 + 1
			if item[1] == 2:
				cof2 = cof2 + 1
		if cof2 == count2:
			print(3)
			for i in range(1, n + 1):
				if i == U:
					print(1, end=' ')
				elif i == V:
					print(2, end=' ')
				else:
					print(3, end=' ')
			print('')
		elif count == count2:
			print(3)
			for item in di.items():
				if item[1] % 2 == 0:
					ans1 = item[0]
					ans2 = item[1]
					break
			for i in range(1, n + 1):
				if i == U:
					print(1, end=' ')
				elif i == V:
					print(2, end=' ')
				else:
					print(3, end=' ')
			print('')
		else:
			print(2)
			for item in di.items():
				if item[1] % 2 == 1:
					ans = item[0]
					break
			for i in range(1, n + 1):
				if i == ans:
					print(1, end=' ')
				else:
					print(2, end=' ')
			print('')


test_cases = int(input())
for given_testcases in range(test_cases):
	adj_list = {}
	(number_of_vertices, number_of_edges) = input().split()
	number_of_vertices = int(number_of_vertices)
	number_of_edges = int(number_of_edges)
	for given_edges in range(number_of_edges):
		(left_node, right_node) = input().split()
		left_node = int(left_node)
		right_node = int(right_node)
		if adj_list.get(left_node) != None:
			adj_list[left_node][0] = adj_list[left_node][0] + 1
			adj_list[left_node].append(right_node)
		else:
			adj_list[left_node] = [1, right_node]
		if adj_list.get(right_node) != None:
			adj_list[right_node][0] = adj_list[right_node][0] + 1
			adj_list[right_node].append(left_node)
		else:
			adj_list[right_node] = [1, left_node]
	check_child = False
	for iterating_over_keys in adj_list.keys():
		if adj_list[iterating_over_keys][0] % 2 != 1:
			pass
		else:
			check_child = True
	if number_of_edges % 2 == 1:
		if check_child == False:
			print(3)
			current_node_position = 1
			while adj_list.get(current_node_position) == None:
				print(1, end=' ')
				current_node_position += 1
			number_of_edges = number_of_edges - adj_list[current_node_position][0]
			pass_first_iteration = True
			for item in adj_list[current_node_position]:
				if pass_first_iteration == True:
					pass_first_iteration = False
					continue
				adj_list[item][0] -= 1
			print(1, end=' ')
			current_node_position += 1
			check_node = False
			for value in range(current_node_position, number_of_vertices + 1):
				if adj_list.get(value) == None:
					print(1, end=' ')
				elif (number_of_edges - adj_list[value][0]) % 2 == 0:
					if check_node == False:
						print(2, end=' ')
						check_node = True
					else:
						print(3, end=' ')
				else:
					print(3, end=' ')
		else:
			print(2)
			to_check_the_first_odd_degree_node = True
			for iterations in range(1, number_of_vertices + 1):
				if adj_list.get(iterations) == None:
					print(2, end=' ')
				elif adj_list[iterations][0] % 2 == 0:
					print(1, end=' ')
				elif to_check_the_first_odd_degree_node == False:
					print(1, end=' ')
				else:
					print(2, end=' ')
					to_check_the_first_odd_degree_node = False
	else:
		print(1)
		for printing_iterations in range(1, number_of_vertices + 1):
			print(1, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	li = []
	c = [0] * n
	tem = -1
	final = [1] * n
	for j in range(m):
		a = input().split()
		li.append([int(a[0]), int(a[1])])
		c[int(a[0]) - 1] += 1
		c[int(a[1]) - 1] += 1
	if m % 2 == 0:
		print(1)
		print(' '.join((str(j) for j in final)))
		continue
	for j in range(n):
		if c[j] % 2 != 0:
			tem = j
			break
	if tem == -1:
		final[li[0][0] - 1] = 2
		final[li[0][1] - 1] = 3
	else:
		final[tem] = 2
	print(max(final))
	print(' '.join((str(j) for j in final)))


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	array = [0] * n
	graph = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		array[a - 1] += 1
		array[b - 1] += 1
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
	flag = True
	for i in array:
		if i % 2 != 0:
			flag = False
			break
	if m % 2 == 0:
		print(1)
		print(' '.join(['1' for _ in range(n)]))
	elif flag == True:
		this = ['1' for _ in range(n)]
		for j in range(len(array)):
			if len(graph[j]) > 0:
				this[j] = '2'
				this[graph[j][0]] = '3'
				break
		print(3)
		print(' '.join(this))
	else:
		if array[0] % 2 != 0:
			this = ['2' for _ in range(n)]
			this[0] = '1'
		else:
			this = ['1' for _ in range(n)]
			for i in range(n):
				if array[i] % 2 != 0:
					this[i] = '2'
					break
		print(2)
		print(' '.join(this))


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	gph = [[] for i in range(n + 1)]
	cnt = [0 for i in range(n + 1)]
	for __ in range(m):
		(a, b) = map(int, input().split(' '))
		gph[a].append(b)
		gph[b].append(a)
		cnt[a] += 1
		cnt[b] += 1
	if m % 2 == 0:
		print(1)
		ans = [1 for i in range(n)]
		print(*ans)
		continue
	odd = False
	odi = -1
	for (i, c) in enumerate(cnt):
		if c % 2 == 1:
			odd = True
			odi = i
	if odd:
		print(2)
		for i in range(1, n + 1):
			if i == odi:
				print(2, end=' ')
			else:
				print(1, end=' ')
	else:
		print(3)
		for (i, g) in enumerate(gph):
			if len(g) > 0:
				a = i
				b = g[0]
				break
		for i in range(1, n + 1):
			if i == a:
				print(3, end=' ')
			elif i == b:
				print(2, end=' ')
			else:
				print(1, end=' ')
	print()


for T in range(int(input())):
	(vertices, edges) = map(int, input().split())
	d = {}
	for i in range(edges):
		(node, neighbor) = map(int, input().split())
		if node in d.keys():
			d[node].append(neighbor)
		else:
			d[node] = [neighbor]
		if neighbor in d.keys():
			d[neighbor].append(node)
		else:
			d[neighbor] = [node]
	ans = [1] * vertices
	if edges % 2 == 0:
		print(1)
		print(*ans)
	else:
		flag = True
		for (key, values) in d.items():
			if len(values) % 2 != 0:
				ans[key - 1] += 1
				flag = False
				break
		if flag == False:
			print(2)
			print(*ans)
		else:
			count = 1
			for (key, values) in d.items():
				if count == 3:
					break
				if len(values) % 2 == 0:
					ans[key - 1] += count
					count += 1
			print(3)
			print(*ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	u = []
	v = []
	freq = [0] * n
	for i in range(m):
		(x, y) = map(int, input().split())
		u.append(x)
		v.append(y)
		freq[x - 1] += 1
		freq[y - 1] += 1
	flag = 0
	ans = [1] * n
	for i in range(len(freq)):
		if freq[i] % 2 == 1:
			temp = i
			flag = 1
			break
	if m % 2 == 0:
		print(1)
		print(' '.join(list(map(str, ans))))
	elif flag == 0:
		ans[u[0] - 1] = 2
		ans[v[0] - 1] = 3
		print(3)
		print(' '.join(list(map(str, ans))))
	else:
		ans[i] = 2
		print(2)
		print(' '.join(list(map(str, ans))))


t = int(input())
for i in range(t):
	d = []
	l = []
	(n, m) = map(int, input().split())
	for j in range(m):
		(x, y) = map(int, input().split())
		l.append(x)
		l.append(y)
	for j in range(n):
		d.append(0)
	for j in range(len(l)):
		d[l[j] - 1] = d[l[j] - 1] + 1
	for j in range(len(d)):
		d[j] = d[j] % 2
	countz = d.count(0)
	if m % 2 == 0:
		print(1)
		for j in range(n):
			print(1, end=' ')
		print()
	elif countz == len(d):
		print(3)
		for j in range(n):
			if j == x - 1:
				print(2, end=' ')
			elif j == y - 1:
				print(3, end=' ')
			else:
				print(1, end=' ')
		print()
	else:
		print(2)
		for j in range(len(d)):
			if d[j] == 1:
				pos = j
				break
		for j in range(n):
			if j == pos:
				print(2, end=' ')
			else:
				print(1, end=' ')
		print()


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	res = [1 for x in range(n + 1)]
	k = 1
	d = {}
	a = [0 for x in range(n + 1)]
	for i in range(1, n + 1):
		d[i] = []
	for i in range(m):
		(u, v) = map(int, input().split())
		d[u].append(v)
		a[u] += 1
		d[v].append(u)
		a[v] += 1
	if m & 1:
		k2 = 2
		while k2 <= n:
			f = 0
			for i in range(1, n + 1):
				if a[i] & 1:
					res[i] = k2
					f = 1
					break
			if f:
				break
			min_i = n
			min_j = 0
			for i in range(1, n + 1):
				if a[i] and a[i] < min_i:
					min_i = a[i]
					min_j = i
			for j in d[min_j]:
				d[j].remove(min_j)
				a[j] -= 1
			d[min_j] = []
			a[min_j] = 0
			res[min_j] = k2
			k2 += 1
		k = k2
	print(k)
	for i in range(1, n + 1):
		print(res[i], end=' ')


import sys
if 'PyPy' in sys.version:
	from _continuation import continulet
else:
	import threading

def dfs(node, vis, deg, grp, oddnode):
	if vis[node]:
		return
	vis[node] = True
	if deg[node] % 2 == 1:
		oddnode.append(node)
	for everyVertex in grp[node]:
		if not vis[everyVertex]:
			dfs(everyVertex, vis, deg, grp, oddnode)

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split(' '))
		grp = []
		for i in range(n + 1):
			li = []
			grp.append(li)
		(arr, s, deg, vis, oddnode) = ([1] * (n + 1), [1], [0] * (n + 1), [False] * (n + 1), [])
		for i in range(m):
			(p, q) = map(int, input().split(' '))
			grp[p].append(q)
			grp[q].append(p)
			deg[p] += 1
			deg[q] += 1
		for i in range(1, n + 1):
			if not vis[i]:
				dfs(i, vis, deg, grp, oddnode)
		totalEdgeCount = sum(deg) // 2
		if totalEdgeCount % 2 == 1:
			if oddnode:
				s.append(2)
				arr[oddnode[0]] = 2
			else:
				s.append(2)
				s.append(3)
				for i in range(1, n + 1):
					if len(grp[i]):
						arr[i] = 2
						arr[grp[i][0]] = 3
						break
		print(len(s))
		print(*arr[1:])
if 'PyPy' in sys.version:

	def bootstrap(cont):
		(call, arg) = cont.switch()
		while True:
			(call, arg) = cont.switch(to=continulet(lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()
else:
	sys.setrecursionlimit(1 << 30)
	threading.stack_size(1 << 27)
	main_thread = threading.Thread(target=main)
	main_thread.start()
	main_thread.join()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	V = [[] for j in range(n + 1)]
	arr = []
	ans2 = [0 for j in range(n + 1)]
	ans = [1 for j in range(n + 1)]
	for j in range(m):
		(a, b) = map(int, input().split())
		l = [a, b]
		V[a].append(b)
		arr.append(a)
		arr.append(b)
		ans2[a] += 1
		ans2[b] += 1
	flag = 0
	if m % 2 == 0:
		print('1')
		for j in range(n):
			print('1', end=' ')
	elif m % 2 == 1:
		for j in range(1, n + 1):
			if ans2[j] % 2 != 0:
				ans[j] = 2
				flag = 1
				break
		if flag == 1:
			print('2')
			for j in range(1, n + 1):
				print(ans[j], end=' ')
		else:
			for j in range(1, n + 1):
				if len(V[j]) != 0:
					ans[j] = 2
					ans[V[j][0]] = 3
					break
			print('3')
			for j in range(1, n + 1):
				print(ans[j], end=' ')


t = int(input())
for j in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	li1 = []
	temp = 0
	if m % 2 == 0:
		st = ''
		for u in range(m):
			(x, y) = input().split()
		for o in range(n):
			st = st + '1 '
		print('1')
		print(st)
	else:
		st = ''
		li2 = [0] * n
		for p in range(m):
			(x, y) = input().split()
			x = int(x)
			y = int(y)
			li2[x - 1] = li2[x - 1] + 1
			li2[y - 1] = li2[y - 1] + 1
			li1.append([x, y])
		fl = 0
		for k in range(n):
			if li2[k] % 2 == 1 and fl == 0:
				st = st + '1 '
				fl = 1
			else:
				st = st + '2 '
		if fl == 1:
			print('2')
			print(st)
		else:
			li_final = [0] * n
			for i in range(n):
				if li2[i] == 0:
					li_final[i] = 1
				else:
					li_final[i] = 3
			li_final[li1[0][1] - 1] = 2
			li_final[li1[0][0] - 1] = 1
			s = ''
			for i in range(n):
				s = s + str(li_final[i]) + ' '
			print('3')
			print(s)


try:
	t = int(input())
	for i in range(t):
		(n, m) = map(int, input().split())
		l = [0] * n
		for j in range(m):
			(o, p) = map(int, input().split())
			l[o - 1] = l[o - 1] + 1
			l[p - 1] = l[p - 1] + 1
		if m % 2 == 0:
			print(1)
			print('1 ' * n)
		else:
			flag = 0
			jj = 0
			for j in range(n):
				if l[j] % 2 != 0:
					flag = 1
					jj = j + 1
					break
			if flag == 0:
				print(3)
				for j in range(n):
					if j == o - 1:
						l[j] = 2
					elif j == p - 1:
						l[j] = 3
					else:
						l[j] = 1
				print(' '.join(map(str, l)))
			else:
				b = []
				print(2)
				b = [1] * (jj - 1) + [2] + [1] * (n - jj)
				print(' '.join(map(str, b)))
except:
	pass


t = int(input())
while t != 0:
	x = input()
	l = list(map(int, x.split(' ')))
	n = l[0]
	e = l[1]
	li = [0] * n
	flag = 0
	brek = 0
	for i in range(0, e):
		k = list(map(int, input().split(' ')))
		v1 = k[0] - 1
		v2 = k[1] - 1
		li[v1] += 1
		li[v2] += 1
	if e % 2 == 0:
		print('1')
		print('1 ' * n)
	else:
		for i in range(0, n):
			if li[i] % 2 != 0:
				print('2')
				print('1 ' * i, end='')
				brek = i
				print('2', end=' ')
				print('1 ' * (n - i - 1), end=' ')
				flag = 0
				break
			else:
				flag = 1
		if flag == 1:
			print('3')
			for i in range(0, n):
				if i == v1:
					print('2', end=' ')
				elif i == v2:
					print('3', end=' ')
				else:
					print('1', end=' ')
	t = t - 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = {}
	temp = []
	s = set()
	for i in range(1, n + 1):
		f[i] = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		temp = [a, b]
		f[a] += 1
		f[b] += 1
	if m % 2 == 0:
		print(1)
		print(*[1 for i in range(n)])
	else:
		flag = 0
		cur = 0
		for i in f:
			if f[i] % 2:
				flag = 1
				cur = i
				break
		if flag:
			print(2)
			for i in range(1, n + 1):
				if i == cur:
					print(2, end=' ')
				else:
					print(1, end=' ')
		else:
			print(3)
			for i in range(1, n + 1):
				if i == temp[0]:
					print(2, end=' ')
				elif i == temp[1]:
					print(3, end=' ')
				else:
					print(1, end=' ')
		print()


from collections import defaultdict
t = int(input())
while t != 0:
	t = t - 1
	h = 0
	(n, m) = list(map(int, input().split()))
	d1 = defaultdict(lambda : h)
	q = list()
	c = -1
	f1 = 0
	p = list()
	z = list()
	for o in range(0, m):
		(a1, b1) = list(map(int, input().split()))
		p.append([a1, b1])
		d1[a1] = d1[a1] + 1
		d1[b1] = d1[b1] + 1
	if m % 2 == 0:
		f1 = 1
		q = [1] * n
		print(1)
		for i in q:
			print(i, end=' ')
		continue
	else:
		for i in range(1, n + 1):
			if d1[i] % 2 == 1:
				c = i
				break
		if c != -1:
			f1 = 1
			z = [1] * n
			z[c - 1] = 2
			print(2)
			for i in z:
				print(i, end=' ')
		if f1 == 0:
			for i in range(1, n + 1):
				if d1[i] % 2 == 0 and d1[i] > 0:
					c1 = i
					for (t1, y1) in p:
						if t1 == c1:
							c2 = y1
							break
						if y1 == c1:
							c2 = t1
							break
					break
			z = [1] * n
			z[c1 - 1] = 2
			z[c2 - 1] = 3
			print(3)
			for i in z:
				print(i, end=' ')