package main

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

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+1)
		for i := 0; i < m; i++ {
			var u, v int
			fmt.Fscan(in, &u, &v)
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}

		visited := make([]bool, n+1)
		parent := make([]int, n+1)
		var cycle []int

		var dfsCycle func(int, int) bool
		dfsCycle = func(v, p int) bool {
			visited[v] = true
			parent[v] = p
			for _, to := range adj[v] {
				if to == p {
					continue
				}
				if visited[to] {
					curr := v
					cycle = append(cycle, to)
					for curr != to {
						cycle = append(cycle, curr)
						curr = parent[curr]
					}
					return true
				}
				if dfsCycle(to, v) {
					return true
				}
			}
			return false
		}

		hasCycle := false
		for i := 1; i <= n; i++ {
			if !visited[i] {
				if dfsCycle(i, -1) {
					hasCycle = true
					break
				}
			}
		}

		if hasCycle {
			fmt.Fprintln(out, "YES")
			ans := make([]int, n+1)
			for _, v := range cycle {
				ans[v] = 1
			}
			for i := 1; i <= n; i++ {
				if i > 1 {
					fmt.Fprint(out, " ")
				}
				fmt.Fprint(out, ans[i])
			}
			fmt.Fprintln(out)
			continue
		}

		visitedComp := make([]bool, n+1)
		solved := false

		for i := 1; i <= n; i++ {
			if visitedComp[i] {
				continue
			}

			var comp []int
			var dfsComp func(int)
			dfsComp = func(v int) {
				visitedComp[v] = true
				comp = append(comp, v)
				for _, to := range adj[v] {
					if !visitedComp[to] {
						dfsComp(to)
					}
				}
			}
			dfsComp(i)

			deg4 := -1
			for _, v := range comp {
				if len(adj[v]) >= 4 {
					deg4 = v
					break
				}
			}

			if deg4 != -1 {
				fmt.Fprintln(out, "YES")
				ans := make([]int, n+1)
				ans[deg4] = 2
				for j := 0; j < 4; j++ {
					ans[adj[deg4][j]] = 1
				}
				for j := 1; j <= n; j++ {
					if j > 1 {
						fmt.Fprint(out, " ")
					}
					fmt.Fprint(out, ans[j])
				}
				fmt.Fprintln(out)
				solved = true
				break
			}

			var deg3 []int
			for _, v := range comp {
				if len(adj[v]) == 3 {
					deg3 = append(deg3, v)
				}
			}

			if len(deg3) >= 2 {
				u, v := deg3[0], deg3[1]
				var path []int
				var find func(int, int, int, []int) bool
				find = func(curr, target, p int, currPath []int) bool {
					currPath = append(currPath, curr)
					if curr == target {
						path = make([]int, len(currPath))
						copy(path, currPath)
						return true
					}
					for _, nxt := range adj[curr] {
						if nxt != p {
							if find(nxt, target, curr, currPath) {
								return true
							}
						}
					}
					return false
				}
				find(u, v, -1, []int{})

				ans := make([]int, n+1)
				for _, p := range path {
					ans[p] = 2
				}
				uNeigh := 0
				for _, nxt := range adj[u] {
					if nxt != path[1] {
						ans[nxt] = 1
						uNeigh++
						if uNeigh == 2 {
							break
						}
					}
				}
				vNeigh := 0
				for _, nxt := range adj[v] {
					if nxt != path[len(path)-2] {
						ans[nxt] = 1
						vNeigh++
						if vNeigh == 2 {
							break
						}
					}
				}
				fmt.Fprintln(out, "YES")
				for j := 1; j <= n; j++ {
					if j > 1 {
						fmt.Fprint(out, " ")
					}
					fmt.Fprint(out, ans[j])
				}
				fmt.Fprintln(out)
				solved = true
				break
			}

			if len(deg3) == 1 {
				u := deg3[0]
				var arms [][]int
				for _, nxt := range adj[u] {
					var arm []int
					curr := nxt
					p := u
					for {
						arm = append(arm, curr)
						moved := false
						for _, nn := range adj[curr] {
							if nn != p {
								p = curr
								curr = nn
								moved = true
								break
							}
						}
						if !moved {
							break
						}
					}
					arms = append(arms, arm)
				}

				sort.Slice(arms, func(i, j int) bool {
					return len(arms[i]) < len(arms[j])
				})

				if len(arms[0]) >= 2 && len(arms[1]) >= 2 && len(arms[2]) >= 2 {
					ans := make([]int, n+1)
					ans[u] = 3
					for j := 0; j < 3; j++ {
						ans[arms[j][0]] = 2
						ans[arms[j][1]] = 1
					}
					fmt.Fprintln(out, "YES")
					for j := 1; j <= n; j++ {
						if j > 1 {
							fmt.Fprint(out, " ")
						}
						fmt.Fprint(out, ans[j])
					}
					fmt.Fprintln(out)
					solved = true
					break
				}

				if len(arms[0]) >= 1 && len(arms[1]) >= 3 && len(arms[2]) >= 3 {
					ans := make([]int, n+1)
					ans[u] = 4
					ans[arms[0][0]] = 2
					for j := 1; j <= 2; j++ {
						ans[arms[j][0]] = 3
						ans[arms[j][1]] = 2
						ans[arms[j][2]] = 1
					}
					fmt.Fprintln(out, "YES")
					for j := 1; j <= n; j++ {
						if j > 1 {
							fmt.Fprint(out, " ")
						}
						fmt.Fprint(out, ans[j])
					}
					fmt.Fprintln(out)
					solved = true
					break
				}

				if len(arms[0]) >= 1 && len(arms[1]) >= 2 && len(arms[2]) >= 5 {
					ans := make([]int, n+1)
					ans[u] = 6
					ans[arms[0][0]] = 3
					ans[arms[1][0]] = 4
					ans[arms[1][1]] = 2
					ans[arms[2][0]] = 5
					ans[arms[2][1]] = 4
					ans[arms[2][2]] = 3
					ans[arms[2][3]] = 2
					ans[arms[2][4]] = 1
					fmt.Fprintln(out, "YES")
					for j := 1; j <= n; j++ {
						if j > 1 {
							fmt.Fprint(out, " ")
						}
						fmt.Fprint(out, ans[j])
					}
					fmt.Fprintln(out)
					solved = true
					break
				}
			}
		}

		if !solved {
			fmt.Fprintln(out, "NO")
		}
	}
}