package main

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

const maxN = 1000005

var (
	head    = make([]int, maxN)
	to      = make([]int, 2*maxN)
	nextArr = make([]int, 2*maxN)
	parent  = make([]int, maxN)
	depth   = make([]int, maxN)
	color   = make([]int, maxN)
	C_cov   = make([]int, maxN)
	NC_cov  = make([]int, maxN)
	visited = make([]bool, maxN)
	flip    = make([]bool, maxN)
	order   = make([]int, 0, maxN)
	stack   = make([]State, 0, maxN)
)

type State struct {
	u, edge int
}

var reader *bufio.Reader
var out *bufio.Writer

func readInt() int {
	res := 0
	b, err := reader.ReadByte()
	if err != nil {
		return 0
	}
	for b < '0' || b > '9' {
		b, err = reader.ReadByte()
		if err != nil {
			return 0
		}
	}
	for '0' <= b && b <= '9' {
		res = res*10 + int(b-'0')
		b, err = reader.ReadByte()
		if err != nil {
			break
		}
	}
	return res
}

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

	t := readInt()
	for tc := 0; tc < t; tc++ {
		n := readInt()
		m := readInt()

		for i := 1; i <= n; i++ {
			head[i] = -1
			visited[i] = false
			flip[i] = false
			C_cov[i] = 0
			NC_cov[i] = 0
		}

		edgeIdx := 0
		for i := 0; i < m; i++ {
			u := readInt()
			v := readInt()

			to[edgeIdx] = v
			nextArr[edgeIdx] = head[u]
			head[u] = edgeIdx
			edgeIdx++

			to[edgeIdx] = u
			nextArr[edgeIdx] = head[v]
			head[v] = edgeIdx
			edgeIdx++
		}

		order = order[:0]
		stack = stack[:0]

		stack = append(stack, State{1, head[1]})
		visited[1] = true
		parent[1] = 0
		depth[1] = 0
		color[1] = 0

		C := 0
		var conflict_edge [2]int

		for len(stack) > 0 {
			curr := &stack[len(stack)-1]
			u := curr.u
			e := curr.edge

			if e != -1 {
				v := to[e]
				curr.edge = nextArr[e]

				if !visited[v] {
					visited[v] = true
					parent[v] = u
					depth[v] = depth[u] + 1
					color[v] = 1 - color[u]
					stack = append(stack, State{v, head[v]})
				} else if v != parent[u] && depth[v] < depth[u] {
					if color[u] == color[v] {
						C++
						C_cov[u]++
						C_cov[v]--
						conflict_edge = [2]int{u, v}
					} else {
						NC_cov[u]++
						NC_cov[v]--
					}
				}
			} else {
				order = append(order, u)
				stack = stack[:len(stack)-1]
			}
		}

		if C == 0 {
			fmt.Fprintln(out, "YES")
			for i := 1; i <= n; i++ {
				if color[i] == 1 {
					out.WriteByte('1')
				} else {
					out.WriteByte('0')
				}
			}
			out.WriteByte('\n')
		} else if C == 1 {
			fmt.Fprintln(out, "YES")
			c := color[conflict_edge[0]]
			for i := 1; i <= n; i++ {
				if color[i] == c {
					out.WriteByte('1')
				} else {
					out.WriteByte('0')
				}
			}
			out.WriteByte('\n')
		} else {
			for i := 0; i < n; i++ {
				u := order[i]
				if parent[u] != 0 {
					C_cov[parent[u]] += C_cov[u]
					NC_cov[parent[u]] += NC_cov[u]
				}
			}

			found := -1
			for i := 1; i <= n; i++ {
				if parent[i] != 0 && C_cov[i] == C && NC_cov[i] == 0 {
					found = i
					break
				}
			}

			if found != -1 {
				flip[found] = true
				for i := n - 1; i >= 0; i-- {
					u := order[i]
					if parent[u] != 0 && flip[parent[u]] {
						flip[u] = true
					}
				}
				for i := 1; i <= n; i++ {
					if flip[i] {
						color[i] = 1 - color[i]
					}
				}

				fmt.Fprintln(out, "YES")
				c := color[found]
				for i := 1; i <= n; i++ {
					if color[i] == c {
						out.WriteByte('1')
					} else {
						out.WriteByte('0')
					}
				}
				out.WriteByte('\n')
			} else {
				fmt.Fprintln(out, "NO")
			}
		}
	}
}