package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}

	for tc := 0; tc < t; tc++ {
		var n, m int
		fmt.Fscan(in, &n, &m)

		adj := make([][]int, n)
		for i := 0; i < m; i++ {
			var u, v int
			fmt.Fscan(in, &u, &v)
			u--
			v--
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}

		allEven := true
		for i := 0; i < n; i++ {
			if len(adj[i])%2 != 0 {
				allEven = false
				break
			}
		}

		if allEven {
			fmt.Fprintln(out, 1)
			for i := 0; i < n; i++ {
				if i > 0 {
					fmt.Fprint(out, " ")
				}
				fmt.Fprint(out, 1)
			}
			fmt.Fprintln(out)
			continue
		}

		words := (n + 1 + 63) / 64
		matrix := make([][]uint64, n)
		for i := 0; i < n; i++ {
			matrix[i] = make([]uint64, words)
			degree := len(adj[i])
			for _, neighbor := range adj[i] {
				matrix[i][neighbor/64] |= 1 << (neighbor % 64)
			}
			if degree%2 != 0 {
				matrix[i][i/64] |= 1 << (i % 64)
				matrix[i][n/64] |= 1 << (n % 64)
			}
		}

		r := 0
		pivots := make([]int, n)
		for i := 0; i < n; i++ {
			pivots[i] = -1
		}

		for c := 0; c < n; c++ {
			p := -1
			for i := r; i < n; i++ {
				if (matrix[i][c/64] & (1 << (c % 64))) != 0 {
					p = i
					break
				}
			}
			if p == -1 {
				continue
			}

			matrix[r], matrix[p] = matrix[p], matrix[r]

			for i := 0; i < n; i++ {
				if i != r && (matrix[i][c/64]&(1<<(c%64))) != 0 {
					for w := 0; w < words; w++ {
						matrix[i][w] ^= matrix[r][w]
					}
				}
			}
			pivots[r] = c
			r++
		}

		ans := make([]int, n)
		for i := 0; i < r; i++ {
			c := pivots[i]
			if (matrix[i][n/64] & (1 << (n % 64))) != 0 {
				ans[c] = 1
			}
		}

		fmt.Fprintln(out, 2)
		for i := 0; i < n; i++ {
			if i > 0 {
				fmt.Fprint(out, " ")
			}
			fmt.Fprint(out, ans[i]+1)
		}
		fmt.Fprintln(out)
	}
}