You are given a connected undirected graph consisting of $n$ vertices and $m$ edges. There are no self-loops or multiple edges in the given graph.

You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).


-----Input-----

The first line contains two integer numbers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le 2 \cdot 10^5$) — the number of vertices and edges, respectively.

The following $m$ lines contain edges: edge $i$ is given as a pair of vertices $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). There are no multiple edges in the given graph, i. e. for each pair ($u_i, v_i$) there are no other pairs ($u_i, v_i$) and ($v_i, u_i$) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).


-----Output-----

If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line.

Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length $m$. The $i$-th element of this string should be '0' if the $i$-th edge of the graph should be directed from $u_i$ to $v_i$, and '1' otherwise. Edges are numbered in the order they are given in the input.


-----Example-----
Input
6 5
1 5
2 1
1 4
3 1
6 1

Output
YES
10100



-----Note-----

The picture corresponding to the first example: [Image]

And one of possible answers: $\text{of}$

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
from __future__ import print_function
import itertools, os, sys, threading

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
from collections import deque, Counter, OrderedDict, defaultdict
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[1]

def sort2(l):
	return sorted(l, key=getKey, reverse=True)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def ceil(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
g = defaultdict(list)
color = [-1] * 200005

def bfs(n):
	for i in range(n):
		if color[i] == -1:
			color[i] = 0
			Q = [(i, 0)]
			while Q:
				(node, c) = Q.pop()
				for nei in g[node]:
					if color[nei] == -1:
						color[nei] = 1 - c
						Q.append((nei, 1 - c))
					elif color[nei] != 1 - c:
						print('NO')
						exit()

def main():
	(n, m) = mi()
	u = [0] * 200005
	for i in range(m):
		(x, y) = mi()
		u[i] = x
		g[x].append(y)
		g[y].append(x)
	bfs(n)
	print('YES')
	ans = ''
	for i in range(m):
		print(color[u[i]], end='')
main()


import os
from collections import deque, defaultdict

def isbipartite(col, g):
	col[1] = 0
	q = deque()
	q.append(1)
	bipartite = True
	while q:
		v = q.popleft()
		for i in range(0, len(g[v])):
			if col[g[v][i]] == -1:
				col[g[v][i]] = col[v] ^ 1
				q.append(g[v][i])
			else:
				bipartite = bipartite & (col[g[v][i]] != col[v])
	return bipartite

def main():
	N = 200100
	g = defaultdict(list)
	col = [-1] * N
	src = []
	dest = []
	(n, m) = map(int, input().split(' '))
	for i in range(0, m):
		(s, d) = map(int, input().split(' '))
		g[s].append(d)
		g[d].append(s)
		src.append(s)
		dest.append(d)
	edges = list(zip(src, dest))
	if not isbipartite(col, g):
		print('NO')
		exit(0)
	ans = ''
	for i in range(0, m):
		if col[edges[i][0]] == 0:
			ans = ans + '1'
		else:
			ans = ans + '0'
	print('YES')
	print(ans)
main()


def dostuff(d, q):
	stopped = False
	while q:
		(v, inc) = q.pop()
		for edge in neighs[v]:
			if edge in d:
				if d[edge] != v if inc else d[edge] == v:
					q = []
					stopped = True
					break
			else:
				d[edge] = v if inc else other(edge, v)
				q.append((other(edge, v), not inc))
	return (not stopped, d)

def other(edge, c):
	return edge[1] if edge[0] == c else edge[0]

def string(order, d):
	ls = []
	for k in order:
		ls.append(int(d[k] == k[0]))
	return ''.join(map(str, ls))
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, m) = kk()
neighs = [[] for _ in range(n)]
order = []
for _ in range(m):
	(n1, n2) = k2()
	neighs[n1].append((n1, n2))
	neighs[n2].append((n1, n2))
	order.append((n1, n2))
d = {(n1, n2): n1}
q = [(n1, True), (n2, False)]
(ok, d) = dostuff(d, q)
if ok:
	print('YES')
	print(string(order, d))
	exit()
d = {(n1, n2): n2}
q = [(n2, True), (n1, False)]
(ok, d) = dostuff(d, q)
if ok:
	print('YES')
	print(string(order, d))
	exit()
print('NO')


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
from collections import defaultdict
import sys
(n, m) = f()

@bootstrap
def dfs(node, c=0):
	v[node] = 1
	co[node] = c
	for j in g[node]:
		if v[j] == 0:
			if (yield dfs(j, c ^ 1)) == False:
				yield False
		elif co[node] == co[j]:
			yield False
	yield True
g = defaultdict(list)
u = [0] * (200000 + 1)
for i in range(1, m + 1):
	(a, b) = f()
	u[i] = a
	g[a].append(b)
	g[b].append(a)
v = [0] * (200000 + 1)
co = [0] * (200000 + 1)
if dfs(1, 0):
	print('YES')
	for i in range(1, m + 1):
		if co[u[i]] == 0:
			print(0, end='')
		else:
			print(1, end='')
else:
	print('NO')


import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def input_as_list():
	return list(map(int, input().split()))

def array_of(f, *dim):
	return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
	(n, m) = input_as_list()
	G = array_of(list, n)
	E = []
	for _ in range(m):
		(u, v) = input_as_list()
		(u, v) = (u - 1, v - 1)
		G[u].append(v)
		G[v].append(u)
		E.append((u, v))
	depth = array_of(int, n)
	visited = array_of(bool, n)
	visited[0] = True
	stack = [0]
	while stack:
		u = stack.pop()
		for v in G[u]:
			if visited[v]:
				if depth[u] % 2 == depth[v] % 2:
					print('NO')
					return
			else:
				depth[v] = depth[u] + 1
				visited[v] = True
				stack.append(v)
	out = []
	for (u, v) in E:
		out.append(str(depth[u] % 2))
	print('YES')
	print(''.join(out))
main()


(n, e) = [int(x) for x in input().split()]
arr = [[] for x in range(0, n + 1)]
edge = []
for i in range(0, e):
	(u, v) = [int(x) for x in input().split()]
	edge.append([u, v])
	arr[u].append(v)
	arr[v].append(u)
visited = [0 for i in range(0, n + 1)]
color = [-1 for i in range(0, n + 1)]
sol_list = []

def BFS(s):
	visited[s] = 1
	sol_list.append([s])
	color[s] = 0
	while True:
		temp = []
		for u in sol_list[-1]:
			for v in arr[u]:
				if not visited[v]:
					visited[v] = 1
					color[v] = len(sol_list) % 2
					temp.append(v)
		if len(temp) == 0:
			break
		sol_list.append(temp)
BFS(1)
for element in edge:
	if color[element[0]] == color[element[1]]:
		print('NO')
		exit()
print('Yes')
for element in edge:
	print(color[element[0]], end='')


(n, m) = map(int, input().split())
g = [False] * (n + 1)
t = [False] * (n + 1)
ide = {}
graf = []
for i in range(n):
	ide[i + 1] = []
for i in range(m):
	(u, v) = map(int, input().split())
	graf.append((u, v))
	ide[u].append(v)
	ide[v].append(u)
ch = [False] * (n + 1)
ifb = [1]
fr = 0
while fr < len(ifb):
	u = ifb[fr]
	ch[u] = True
	for v in ide[u]:
		if ch[v]:
			continue
		ifb.append(v)
		if g[u] and g[v] or (t[u] and t[v]):
			print('NO')
			exit()
		if g[u] and t[v] or (t[u] and g[v]):
			continue
		if g[u]:
			t[v] = True
			continue
		if t[u]:
			g[v] = True
			continue
		if g[v]:
			t[u] = True
			continue
		if t[v]:
			g[u] = True
			continue
		g[u] = True
		t[v] = True
	fr += 1
print('YES')
for (u, v) in graf:
	if g[u] and t[v]:
		print(1, end='')
	else:
		print(0, end='')
print()


import sys
input = sys.stdin.readline
from collections import deque

class UnDirectedGraph:

	def __init__(self, N, M):
		self.V = N
		self.E = M
		self.edge = [[] for _ in range(self.V)]
		self.edges = [0] * self.E
		self.visited = [False] * self.V
		self.color = [-1] * self.V

	def add_edges(self, ind=1):
		for i in range(self.E):
			(a, b) = map(int, input().split())
			a -= ind
			b -= ind
			self.edge[a].append(b)
			self.edge[b].append(a)
			self.edges[i] = (a, b)

	def dfs(self, start):
		stack = deque([start])
		self.color[start] = 0
		while stack:
			v = stack.pop()
			for u in self.edge[v]:
				if self.color[u] == -1:
					stack.append(u)
					self.color[u] = self.color[v] ^ 1
				if self.color[u] == self.color[v]:
					return False
		return True
(N, M) = map(int, input().split())
G = UnDirectedGraph(N, M)
G.add_edges(1)
if G.dfs(0):
	print('YES')
	ans = ''
	for i in range(M):
		ans += str(G.color[G.edges[i][0]])
	print(ans)
else:
	print('NO')


from collections import deque

def odd_cycle(a, vertex):
	(s, colors) = ([1] * len(a), [1] * len(a))
	d = deque([vertex])
	s[vertex] = colors[vertex] = 0
	while len(d) > 0:
		q = d.popleft()
		for q1 in a[q]:
			if s[q1]:
				d.append(q1)
				colors[q1] = 2 - colors[q]
				s[q] = 0
			elif 2 - colors[q] != colors[q1]:
				return (False, [])
	return (True, colors)
(n, m) = map(int, input().split())
edges = []
d = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	d[x].append(y)
	d[y].append(x)
	edges.append([x, y])
s = odd_cycle(d, 1)
ans = []
if s[0]:
	s = s[1]
	print('YES')
	for q in edges:
		if s[q[0]] == 0:
			ans.append('0')
		else:
			ans.append('1')
	print(''.join(ans))
else:
	print('NO')


from collections import defaultdict
(n, m) = [int(i) for i in input().split()]
adj = defaultdict(set)
edge_order = []
visited = [False for i in range(n)]
color = [0 for i in range(n)]
for j in range(m):
	(u, v) = [int(i) - 1 for i in input().split()]
	adj[u].add(v)
	adj[v].add(u)
	edge_order.append((u, v))

def check_bipartite():
	queue = []
	queue.append(0)
	while queue:
		v = queue.pop()
		for u in adj[v]:
			if not visited[u]:
				visited[u] = True
				color[u] = (color[v] + 1) % 2
				queue.append(u)
			elif color[u] == color[v]:
				return False
	return True
if check_bipartite():
	print('YES')
	ans = ''
	for (u, v) in edge_order:
		if color[u] > color[v]:
			ans += '1'
		else:
			ans += '0'
	print(ans)
else:
	print('NO')


from collections import defaultdict as DD
from bisect import bisect_left as BL
from bisect import bisect_right as BR
from itertools import combinations as IC
from itertools import permutations as IP
from random import randint as RI
import sys
MOD = pow(10, 9) + 7

def IN(f=0):
	if f == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())

def bfs(s):
	i = 1
	parent[s] = -1
	vis[s] = 1
	frontier = [s]
	while frontier:
		nex = []
		for u in frontier:
			for v in d[u]:
				if vis[v] == 0:
					vis[v] = 1
					color[v] = color[u] ^ 1
					parent[v] = u
					nex.append(v)
		frontier = nex
		i += 1
	return parent
(n, m) = IN()
d = DD(list)
d1 = []
for i in range(m):
	(u, v) = IN()
	d[u].append(v)
	d[v].append(u)
	d1.append([u, v])
vis = [0 for i in range(n + 1)]
color = [0 for i in range(n + 1)]
parent = dict()
for i in range(1, n + 1):
	if vis[i] == 0:
		bfs(i)
flag = 0
for i in d:
	for j in d[i]:
		if color[j] != color[i] ^ 1:
			flag = 1
			break
	if flag == 1:
		break
if flag == 1:
	print('NO')
else:
	ans = ''
	for (i, j) in d1:
		if color[i] == 0 and color[j] == 1:
			ans += str(1)
		else:
			ans += str(0)
	print('YES')
	print(ans)


import math
import bisect

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, x, y) = egcd(b % a, a)
		return (g, y - b // a * x, x)

def mulinv(b, n):
	(g, x, _) = egcd(b, n)
	if g == 1:
		return x % n
primes = []

def isprime(n):
	for d in range(2, int(math.sqrt(n)) + 1):
		if n % d == 0:
			return False
	return True

def argsort(ls):
	return sorted(range(len(ls)), key=ls.__getitem__)

def f(p=0):
	if p == 1:
		return map(int, input().split())
	elif p == 2:
		return list(map(int, input().split()))
	else:
		return int(input())
(n, m) = f(1)
g = [list() for _ in range(n + 1)]
ver = [-1] * (n + 1)
dl = [-1] * m
edges = [0] * m
vdl = [0] * (n + 1)
for i in range(m):
	(u, v) = f(1)
	g[u].append(i)
	g[v].append(i)
	edges[i] = (u, v)
queue = [1]
orient = 1
ver[1] = 1
for i in range(1, n + 1):
	if vdl[i] == 0:
		vdl[i] = 1
		queue = [i]
		ver[i] = 0
		for u in queue:
			for edge in g[u]:
				pos = 0
				if edges[edge][0] == u:
					pos = 0
				else:
					pos = 1
				if ver[u] == ver[edges[edge][(pos + 1) % 2]]:
					print('NO')
					exit()
				else:
					e = 0
					if ver[u] == 0:
						if pos == 0:
							e = 1
						else:
							e = 0
					elif pos == 0:
						e = 0
					else:
						e = 1
					if dl[edge] != -1 and dl[edge] != e:
						print('NO')
						exit()
					else:
						dl[edge] = e
				if vdl[edges[edge][(pos + 1) % 2]] != 1:
					queue.append(edges[edge][(pos + 1) % 2])
					ver[edges[edge][(pos + 1) % 2]] = (ver[u] + 1) % 2
					vdl[edges[edge][(pos + 1) % 2]] = 1
print('YES')
print(''.join((str(el) for el in dl)))


import sys

def input():
	return sys.stdin.readline()
(n, m) = map(int, input().split())
give = [False] * (n + 1)
take = [False] * (n + 1)
edge = dict()
inputs = []
for i in range(n):
	edge[i + 1] = []
for i in range(m):
	(u, v) = map(int, input().split())
	inputs.append((u, v))
	edge[u].append(v)
	edge[v].append(u)
check = [False] * (n + 1)
queue = [1]
front = 0
while front < len(queue):
	u = queue[front]
	check[u] = True
	for v in edge[u]:
		if check[v]:
			continue
		queue.append(v)
		if give[u] and give[v] or (take[u] and take[v]):
			print('NO')
			return
		if give[u] and take[v] or (take[u] and give[v]):
			continue
		if give[u]:
			take[v] = True
			continue
		if take[u]:
			give[v] = True
			continue
		if give[v]:
			take[u] = True
			continue
		if take[v]:
			give[u] = True
			continue
		give[u] = True
		take[v] = True
	front += 1
print('YES')
for (u, v) in inputs:
	if give[u] and take[v]:
		print(1, end='')
	else:
		print(0, end='')
print()


from collections import deque
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
e = []
for tc in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	e.append((u, v))
	g[u].append(v)
	g[v].append(u)
p = [-1] * n
p[0] = True
yes = True
q = deque([0])
while q:
	f = q.popleft()
	for t in g[f]:
		if p[t] == -1:
			q.append(t)
			p[t] = not p[f]
		elif p[t] == p[f]:
			yes = False
if not yes:
	print('NO')
else:
	print('YES')
	print(''.join(('1' if p[e[i][0]] else '0' for i in range(m))))


from collections import deque

def solve():
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	global max
	max = n * 2
	graph = [[] for _ in range(0, n)]
	distance = [max] * n
	edges = []
	for _ in range(0, m):
		(u, v) = input().split()
		u = int(u) - 1
		v = int(v) - 1
		edges.append(v)
		graph[u].append(v)
		graph[v].append(u)
	if bfs_2k(graph, 0, distance):
		print('YES')
		print(''.join((str(distance[e] % 2) for e in edges)))
	else:
		print('NO')

def bfs_2k(graph, initVertex, dist):
	queue = deque()
	queue.append(initVertex)
	dist[initVertex] = 0
	while queue:
		u = queue.popleft()
		for v in graph[u]:
			if dist[v] == max:
				dist[v] = dist[u] + 1
				queue.append(v)
			if (dist[u] - dist[v]) % 2 == 0:
				return False
	return True
solve()


(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
ind = 0
for e in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append((b - 1, ind, True))
	graph[b - 1].append((a - 1, ind, False))
	ind = ind + 1
paint_array = [-1 for _ in range(n)]
visited = [0 for _ in range(m + 1)]

def paint(vi, color):
	paint_array[vi] = color
	visited[0] = vi
	start = 0
	finish = 1
	paint_ok = True
	while finish != start and paint_ok:
		v = visited[start]
		start = (start + 1) % (m + 1)
		c = paint_array[v]
		for (vi2, ind, orig) in graph[v]:
			if paint_array[vi2] != -1 and paint_array[vi2] != 1 - c:
				paint_ok = False
				break
			if paint_array[vi2] == -1:
				paint_array[vi2] = 1 - c
				visited[finish] = vi2
				finish = (finish + 1) % (m + 1)
	return paint_ok
ok = True
for vi in range(n):
	if paint_array[vi] == -1:
		ok = ok and paint(vi, 0)
if not ok:
	print('NO')
	exit(0)
print('YES')
result = [0 for _ in range(m)]
for vi in range(n):
	for (vi2, ind, orig) in graph[vi]:
		if orig:
			result[ind] = paint_array[vi]
for i in range(m):
	print('0' if result[i] else '1', end='')


import sys
from collections import defaultdict

def main():
	(n, m) = map(int, input().split())
	used = [False] * (n + 1)
	colors = [False] * (n + 1)
	edges = []
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		edges.append((u, v))
		graph[u].append(v)
		graph[v].append(u)
	stack = [1]
	while stack:
		v = stack.pop()
		used[v] = True
		for u in graph[v]:
			if not used[u]:
				colors[u] = not colors[v]
				stack.append(u)
			elif colors[u] == colors[v]:
				print('NO')
				sys.exit()
	print('YES')
	for edge in edges:
		(u, v) = edge
		if colors[u] and (not colors[v]):
			print(1, end='')
		else:
			print(0, end='')
main()


(n, m) = map(int, input().split())
graph = {i: set() for i in range(1, n + 1)}
numreb = {}
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u].add(v)
	graph[v].add(u)
	numreb[u, v] = i

def BFS(digraph, v, m, numreb):
	s2 = set()
	s1 = set()
	ans = [0] * m
	s1.add(v)
	chch = True
	j = {}
	oboid = set()
	fl = 0
	while s1 != set():
		fl = 1 - fl
		for element in s1:
			if element not in oboid:
				oboid.add(element)
				for heh in graph[element]:
					if heh not in oboid:
						if (heh not in j or j[heh] == fl) and (heh, element) in numreb:
							ans[numreb[heh, element]] = fl
							j[heh] = fl
						elif (heh not in j or j[heh] == fl) and (element, heh) in numreb:
							ans[numreb[element, heh]] = 1 - fl
							j[heh] = fl
						else:
							chch = False
				for key in digraph[element]:
					s2.add(key)
		s1 = s2
		s2 = set()
	return [chch, ans]
x = BFS(graph, 1, m, numreb)
if x[0]:
	print('YES')
	print(''.join(list(map(str, x[1]))))
else:
	print('NO')


graph = [[] for _ in range(200000)]
color = [0] * 200000
vis = [0] * 200000

def main():
	(n, m) = map(int, input().split())
	edges = []
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
		edges.append((u, v))
	color[0] = 1
	queue = [(0, 1)]
	i = 0
	while i != len(queue):
		for v in graph[queue[i][0]]:
			if not color[v]:
				color[v] = 3 - queue[i][1]
				queue.append((v, color[v]))
		i += 1
	ans = ['0'] * m
	for i in range(m):
		if color[edges[i][0]] == color[edges[i][1]]:
			print('NO')
			return 0
		if color[edges[i][0]] == 1:
			ans[i] = '1'
	print('YES')
	print(''.join(ans))
main()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd, deque
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
(n, m) = mul()
Adj = [[] for _ in range(n + 1)]
Edges = []
for _ in range(m):
	(u, v) = mul()
	Edges.append((u, v))
	Adj[u].append(v)
	Adj[v].append(u)
Side = [-1] * (n + 1)
Q = deque()
isbipartite = True
for i in range(1, n + 1):
	if Side[i] == -1:
		Q.append(i)
		Side[i] = 1
		while len(Q):
			u = Q.pop()
			for v in Adj[u]:
				if Side[v] == -1:
					Side[v] = Side[u] ^ 1
					Q.append(v)
				else:
					isbipartite &= Side[v] != Side[u]
if not isbipartite:
	print('NO')
else:
	print('YES')
	S = ''
	for (u, v) in Edges:
		if Side[u] == 0:
			S += '0'
		else:
			S += '1'
	print(S)


from __future__ import division, print_function
import io
import os
import sys
from collections import deque
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from cStringIO import StringIO
	from future_builtins import ascii, filter, hex, map, oct, zip
else:
	from io import BytesIO as StringIO
(sys.stdout, stream) = (io.IOBase(), StringIO())
sys.stdout.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
sys.stdout.write = stream.write if sys.version_info[0] < 3 else lambda s: stream.write(s.encode())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)
input = StringIO(os.read(0, os.fstat(0).st_size)).readline

def is_bipartite(graph, start=0):
	n = len(graph)
	bipartite = True
	color = [-1] * n
	color[start] = 0
	visited = [False] * n
	stack = [start]
	while stack:
		start = stack.pop()
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				bipartite &= color[child] != color[start]
				if not visited[child]:
					color[child] = color[start] ^ 1
					stack.append(child)
	return (bipartite, color)

def main():
	(n, m) = map(int, input().split())
	edges = [[int(x) - 1 for x in input().split()] for _ in range(m)]
	graph = [[] for _ in range(n)]
	for edge in edges:
		graph[edge[0]].append(edge[1])
		graph[edge[1]].append(edge[0])
	(bipartite, side) = is_bipartite(graph)
	if not bipartite:
		print('NO')
		return
	print('YES')
	print(*[side[edge[0]] for edge in edges], sep='')
main()


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
EDGE = [list(map(int, input().split())) for i in range(m)]
EDGELIST = [[] for i in range(n + 1)]
for (x, y) in EDGE:
	EDGELIST[x].append(y)
	EDGELIST[y].append(x)
QUE = deque([[1, 1]])
ANS = [-1] * (n + 1)
ANS[1] = 1
while QUE:
	(x, color) = QUE.pop()
	ANS[x] = color
	for to in EDGELIST[x]:
		if ANS[to] == color:
			print('NO')
			return
		if ANS[to] == -1:
			QUE.appendleft([to, abs(color - 1)])
print('YES')
for (x, y) in EDGE:
	if ANS[x] == 1:
		print('1', end='')
	else:
		print('0', end='')


from collections import deque

def isBipartiate(adj, color):
	flip = {0: 1, 1: 0}
	for node in range(1, n + 1):
		if color[node] == -1:
			color[node] = 1
			qu = deque()
			qu.append(node)
			while qu:
				node = qu.popleft()
				for neigh in adj[node]:
					if color[neigh] == -1:
						color[neigh] = flip[color[node]]
						qu.append(neigh)
					elif color[neigh] == color[node]:
						return False
	return True
from collections import defaultdict
(n, m) = map(int, input().split())
adj = defaultdict(list)
edges = []
for _ in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
	edges.append([u, v])
color = [-1] * (n + 1)
if not isBipartiate(adj, color):
	print('NO')
else:
	print('YES')
	for i in range(m):
		print(color[edges[i][0]], end='')


import sys
sys.setrecursionlimit(10000000)
(a, b) = tuple([int(i) for i in input().split()])
save = {}
printl = [''] * b
data = ['']
for i in range(a):
	data.append(set())
for i in range(b):
	a = input().split()
	c = int(a[0])
	d = int(a[1])
	save[c, d] = i
	data[c].add(d)
	data[d].add(c)
done = set()

def search(prev, a, isforward):
	if isforward:
		good = '1'
		bad = '0'
	else:
		good = '0'
		bad = '1'
	for e in data[a]:
		if e in done or e == prev:
			continue
		if (a, e) in save:
			p = save[a, e]
			if printl[p] != '':
				if printl[p] != good:
					print('NO')
					sys.exit()
			else:
				printl[p] = good
				search(a, e, not isforward)
		else:
			p = save[e, a]
			if printl[p] != '':
				if printl[p] != bad:
					print('NO')
					sys.exit()
			else:
				printl[p] = bad
				search(a, e, not isforward)
	done.add(a)
layer = {1}
good = '0'
bad = '1'
while len(layer) > 0:
	(good, bad) = (bad, good)
	new = set()
	for a in layer:
		for e in data[a]:
			if (a, e) in save:
				p = save[a, e]
				if printl[p] != '':
					if printl[p] != good:
						print('NO')
						sys.exit()
				else:
					printl[p] = good
					new.add(e)
			else:
				p = save[e, a]
				if printl[p] != '':
					if printl[p] != bad:
						print('NO')
						sys.exit()
				else:
					printl[p] = bad
					new.add(e)
		layer = new
print('YES')
print(''.join(printl))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())

def is_bipartite(graph, start=0):
	n = len(graph)
	bipartite = True
	color = [-1] * n
	color[start] = 0
	visited = [False] * n
	stack = [start]
	while stack:
		start = stack.pop()
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				bipartite &= color[child] != color[start]
				color[child] = color[start] ^ 1
				if not visited[child]:
					stack.append(child)
	return (bipartite, color)

def main():
	(n, m) = map(int, input().split())
	edges = [[int(x) - 1 for x in input().split()] for _ in range(m)]
	graph = [[] for _ in range(n)]
	for edge in edges:
		graph[edge[0]].append(edge[1])
		graph[edge[1]].append(edge[0])
	(bipartite, side) = is_bipartite(graph)
	if not bipartite:
		print('NO')
		return
	print('YES')
	print(*[side[edge[0]] for edge in edges], sep='')
main()


def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def li():
	return list(mi())
from collections import defaultdict
g = defaultdict(list)
color = [-1] * 200005

def dfs(n):
	color[1] = 0
	stack = [[1, 0]]
	while stack:
		(node, c) = stack.pop()
		for i in g[node]:
			if color[i] == -1:
				stack.append([i, c ^ 1])
				color[i] = c ^ 1
			elif color[i] != c ^ 1:
				print('NO')
				exit()

def main():
	(n, m) = mi()
	u = [0] * (m + 5)
	for i in range(m):
		(x, y) = mi()
		u[i] = x
		g[x].append(y)
		g[y].append(x)
	dfs(n)
	print('YES')
	for i in range(m):
		print(color[u[i]], end='')
main()


import sys, bisect, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def Golf():
	(n, *t) = map(int, open(0).read().split())

def I():
	return int(input())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RA():
	return map(int, open(0).read().split())

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		(a1, ls) = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print((a1, a2), inp)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
l_alp = string.ascii_lowercase
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
show_flg = False
show_flg = True
ans = 0
ans = []
(n, m) = LI()
(g, org) = GI(n, m)
v = [-1 for i in range(n)]

def IsBipartite(edge):
	q = [0]
	v[0] = 0
	while q:
		c = q.pop()
		for (n, d) in edge[c]:
			if v[n] == -1:
				q.append(n)
				v[n] = 1 - v[c]
			elif v[n] == v[c]:
				return (False, [])
	return (True, v)
(ans, v) = IsBipartite(g)
if ans:
	YN(1)
	for (s, t) in org:
		print(v[t - 1], end='')
	print()
else:
	YN(0)


from collections import defaultdict, deque
import bisect
import sys
input = sys.stdin.readline

def bfs(root):
	queue = deque()
	queue.append((root, 0))
	while queue:
		(vertex, dir_) = queue.popleft()
		for child in graph[vertex]:
			if ans[child[0]] == -1:
				ans[child[0]] = 1 - dir_
				queue.append((child[0], 1 - dir_))
			elif ans[child[0]] == dir_:
				print('NO')
				exit()
graph = defaultdict(list)
(n, m) = map(int, input().split())
direction = []
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u].append([v, i])
	graph[v].append([u, i])
	direction.append([u, v])
ans = [-1] * (n + 1)
bfs(1)
output = [0] * m
for i in range(1, n + 1):
	if ans[i] == 1:
		for j in graph[i]:
			if direction[j[1]] == [j[0], i]:
				output[j[1]] = 1
			else:
				output[j[1]] = 0
print('YES')
print(''.join(map(str, output)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque
edge = []

def graph_undirected():
	(n, e) = [int(x) for x in input().split()]
	graph = {}
	for i in range(e):
		(vertex, neighbour) = [int(x) for x in input().split()]
		edge.append([vertex, neighbour])
		if vertex in graph:
			graph[vertex].append(neighbour)
		else:
			graph[vertex] = [neighbour]
		if neighbour in graph:
			graph[neighbour].append(vertex)
		else:
			graph[neighbour] = [vertex]
	return (graph, n)
(graph, n) = graph_undirected()
visited = [False for x in range(n + 1)]
color = [None for x in range(n + 1)]

def cycle_bfs(graph, n, node):
	q = deque([node])
	color[node] = 0
	while q:
		currnode = q.popleft()
		visited[currnode] = True
		if color[currnode] == 0:
			currcolor = 1
		else:
			currcolor = 0
		if currnode in graph:
			for neighbour in graph[currnode]:
				if visited[neighbour] == False:
					visited[neighbour] = True
					color[neighbour] = currcolor
					q.append(neighbour)
				elif color[neighbour] != currcolor:
					return False
	return True
for node in range(1, n + 1):
	if visited[n] == False:
		ans = cycle_bfs(graph, n, node)
		if ans == False:
			break
if ans == True:
	print('YES')
	for (u, v) in edge:
		if color[u] == 1:
			print('0', end='')
		else:
			print('1', end='')
else:
	print('NO')


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

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

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes
from collections import Counter

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		graph = [[] for i in range(n + 1)]
		edges = []
		for i in range(m):
			(a, b) = ria()
			graph[a].append(b)
			graph[b].append(a)
			edges.append([a, b])

		def is_bipartite(graph):
			n = len(graph)
			color = [-1] * n
			for start in range(n):
				if color[start] == -1:
					color[start] = 0
					stack = [start]
					while stack:
						parent = stack.pop()
						for child in graph[parent]:
							if color[child] == -1:
								color[child] = 1 - color[parent]
								stack.append(child)
							elif color[parent] == color[child]:
								return (False, color)
			return (True, color)
		(flag, col) = is_bipartite(graph)
		if flag:
			ws('YES')
			ans = []
			for edge in edges:
				(x, y) = edge
				if col[x] == 1 and col[y] == 0:
					ans.append('1')
				else:
					ans.append('0')
			ws(''.join(ans))
		else:
			ws('NO')
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


(n, m) = map(int, input().strip().split())
graph = dict()
order = dict()
for i in range(m):
	(left, right) = map(int, input().strip().split())
	order[left, right] = i
	if left not in graph:
		graph[left] = set([right])
	else:
		graph[left].add(right)
	if right not in graph:
		graph[right] = set([left])
	else:
		graph[right].add(left)
left_set = {1}
right_set = set()
first = 1
to_process = {1}
ans_dict = dict()
fail = False
while to_process != set():
	temp_list = set()
	for u in to_process:
		for v in set(graph[u]):
			temp_list.add(v)
			if v in left_set:
				fail = True
				break
			right_set.add(v)
			if (u, v) in order:
				ans_dict[order[u, v]] = 0
			else:
				ans_dict[order[v, u]] = 1
			graph[v].remove(u)
			graph[u].remove(v)
	to_process = set()
	for v in temp_list:
		for u in set(graph[v]):
			if u in right_set:
				fail = True
				break
			left_set.add(u)
			to_process.add(u)
			if (v, u) in order:
				ans_dict[order[v, u]] = 1
			else:
				ans_dict[order[u, v]] = 0
			graph[v].remove(u)
			graph[u].remove(v)
		if fail:
			break
	if fail:
		break
if fail:
	print('NO')
else:
	print('YES')
	for i in range(m):
		print(ans_dict[i], end='')


def dostuff(d, q):
	while q:
		(v, inc) = q.pop()
		for e in c[v]:
			oth = e[1] if e[0] == v else e[0]
			if e in d:
				if d[e] != v if inc else d[e] == v:
					return (False, d)
			else:
				d[e] = v if inc else oth
				q.append((oth, not inc))
	return (True, d)

def s(o, d, l=[]):
	for k in o:
		l.append(int(d[k] == k[0]))
	return ''.join(map(str, l))
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
y = lambda : map(lambda x: int(x) - 1, input().split())
(n, m) = y()
(c, o) = ([[] for _ in range(n + 1)], [])
for _ in range(m + 1):
	(a, b) = y()
	c[a].append((a, b))
	c[b].append((a, b))
	o.append((a, b))
(k, d) = dostuff({(a, b): a}, [(a, True), (b, False)])
print('YES\n' + s(o, d) if k else 'NO')


from collections import deque

def isBipartite(V, adj, color):

	def bfs(node):
		q.append(node)
		color[node] = 1
		while q:
			node = q.popleft()
			for ele in adj[node]:
				if color[ele] == -1:
					q.append(ele)
					color[ele] = 1 - color[node]
				elif color[ele] == color[node]:
					return False
		return True
	q = deque()
	for i in range(1, V + 1):
		if color[i] == -1:
			boolean = bfs(i)
			if not boolean:
				return False
	return True
(n, m) = list(map(int, input().split()))
edges = []
for i in range(m):
	(x, y) = list(map(int, input().split()))
	edges.append([x, y])
adj = [[] * (n + 1) for ele in range(n + 1)]
color = [-1] * (n + 1)
for (x, y) in edges:
	adj[x].append(y)
	adj[y].append(x)
if isBipartite(n, adj, color):
	print('Yes')
	for i in range(m):
		print(color[edges[i][0]], end='')
else:
	print('No')


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, m) = LI()
	a = [LI_() for _ in range(m)]
	e = collections.defaultdict(set)
	for (b, c) in a:
		e[b].add(c)
		e[c].add(b)
	v = [None] * n

	def f(i, t):
		if v[i]:
			return
		q = [(i, t)]
		qi = 0
		while qi < len(q):
			(i, t) = q[qi]
			qi += 1
			if v[i]:
				continue
			v[i] = t
			nt = 3 - t
			for c in e[i]:
				q.append((c, nt))
	for i in range(n):
		f(i, 1)
	r = []
	for (b, c) in a:
		if v[b] == v[c]:
			return 'NO'
		r.append(v[b] - 1)
	return 'YES\n' + ''.join(map(str, r))
print(main())


import sys
input = sys.stdin.readline
from collections import deque

def bfs():
	q = deque([0])
	color[0] = 1
	while q:
		v = q.popleft()
		for nv in adj_list[v]:
			if color[nv] == 0:
				color[nv] = -color[v]
				q.append(nv)
			elif color[nv] == color[v]:
				return False
	return True
(n, m) = map(int, input().split())
adj_list = [[] for _ in range(n)]
edges = []
for _ in range(m):
	(u, v) = map(int, input().split())
	adj_list[u - 1].append(v - 1)
	adj_list[v - 1].append(u - 1)
	edges.append((u - 1, v - 1))
color = [0] * n
if not bfs():
	print('NO')
	exit()
ans = []
for (u, v) in edges:
	if color[u] == 1 and color[v] == -1:
		ans.append('1')
	else:
		ans.append('0')
print('YES')
print(''.join(ans))


from typing import List
from collections import defaultdict

class GraphColoring:

	def isTwoColorable(self, edges, numVertices):
		graph = defaultdict(list)
		for (a, b) in edges:
			a = a - 1
			b = b - 1
			na = graph[a]
			nb = graph[b]
			na.append(b)
			nb.append(a)
			graph[a] = na
			graph[b] = nb
		visited = [None] * numVertices
		for v in range(numVertices):
			if visited[v] is not None:
				continue
			q = [v]
			visited[v] = True
			while q:
				curr = q.pop()
				for ne in graph[curr]:
					if visited[ne] is not None:
						if visited[ne] == visited[curr]:
							return (False, [])
					else:
						visited[ne] = not visited[curr]
						q.append(ne)
		directions = [max(visited[a - 1] - visited[b - 1], 0) for (a, b) in edges]
		return (True, directions)
(n, m, *_) = map(int, input().split())
edges = []
for _ in range(m):
	(a, b, *_) = map(int, input().split())
	edges.append([a, b])
gc = GraphColoring()
(isTwoC, coloring) = gc.isTwoColorable(edges, n)
if isTwoC:
	print('YES')
	print(''.join(map(str, map(int, coloring))))
else:
	print('NO')


import sys
from typing import List, Tuple, Dict
DEBUG = len(sys.argv) > 1 and sys.argv[1] == '-d'

def LOG(*argv):
	if DEBUG:
		print(*argv, file=sys.stderr)

def CHECK(cond, err_msg=''):
	if DEBUG:
		assert cond, err_msg

def CHECK_EQ(a, b, err_msg=''):
	CHECK(a == b, err_msg='{} v.s. {} {}'.format(a, b, err_msg))

def readval(typ=int):
	return typ(input())

def readvals(typ=int):
	return list(map(typ, input().split()))

def solve(n: int, m: int, edges: List[Tuple[int, int]]) -> str:
	from collections import defaultdict
	neighbors: Dict[int, List[int]] = defaultdict(list)
	for (u, v) in edges:
		neighbors[u].append(v)
		neighbors[v].append(u)
	LOG('neighbors=', neighbors)
	color: Dict[int, bool] = {1: True}
	(queue, visited) = ([1], set([1]))
	cur_color = True
	while len(queue) > 0:
		next_queue = []
		next_color = not cur_color
		for node in queue:
			for next_node in neighbors[node]:
				if next_node not in visited:
					visited.add(next_node)
					next_queue.append(next_node)
					color[next_node] = next_color
		queue = next_queue
		cur_color = next_color
	solution = ''
	for (u, v) in edges:
		if color[u] == color[v]:
			return 'NO'
		solution += '1' if color[u] is True else '0'
	return f'YES\n{solution}'
(n, m) = readvals()
edges = [readvals() for _ in range(m)]
LOG('edges=', edges)
print(solve(n, m, edges))


from collections import *
from sys import stdin

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges, self.l) = (gdict, [], defaultdict(int))

	def get_vertices(self):
		return list(self.gdict.keys())

	def add_edge(self, node1, node2, w=None):
		self.gdict[node1].append(node2)
		self.gdict[node2].append(node1)
		self.edges.append([node1, node2])

	def bfs_util(self, i):
		(queue, self.visit[i], self.color) = (deque([i]), 1, [0] * (n + 1))
		self.color[i] = 1
		while queue:
			s = queue.popleft()
			for i in self.gdict[s]:
				if self.visit[i] == 0:
					queue.append(i)
					self.visit[i] = 1
					self.color[i] = 3 - self.color[s]
				elif self.color[i] == self.color[s]:
					return False
		return True

	def bfs(self):
		(self.visit, cnt) = (defaultdict(int), 0)
		for i in self.get_vertices():
			if self.visit[i] == 0:
				cnt = self.bfs_util(i)
				break
		(ans, ans2, dis, dis2) = ([], [], set(), set())
		if cnt:
			for (u, v) in g.edges:
				ans.append('0' if self.color[u] == 1 else '1')
			print('YES')
			print(''.join(ans))
		else:
			print('NO')
g = graph()
(n, m) = arr_inp(1)
for i in range(m):
	(u, v) = arr_inp(1)
	g.add_edge(u, v)
g.bfs()


from collections import deque

def bfs_2k(graph, initVertex, color):
	queue = deque()
	queue.append(initVertex)
	color[initVertex] = 0
	while queue:
		u = queue.popleft()
		for v in graph[u]:
			if color[v] == color[u]:
				return False
			if color[v] == -1:
				color[v] = color[u] ^ 1
				queue.append(v)
	return True
(n, m) = input().split()
n = int(n)
m = int(m)
graph = [[] for _ in range(0, n)]
color = [-1] * n
edges = []
for i in range(0, m):
	(u, v) = input().split()
	u = int(u) - 1
	v = int(v) - 1
	edges.append(v)
	graph[u].append(v)
	graph[v].append(u)
if bfs_2k(graph, 0, color):
	print('YES')
	print(''.join((str(color[e]) for e in edges)))
else:
	print('NO')


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def li():
	return list(mi())
from collections import defaultdict
g = defaultdict(list)
color = [-1] * 200005

def dfs(n):
	color[1] = 0
	stack = [[1, 0]]
	while stack:
		(node, c) = stack.pop()
		for i in g[node]:
			if color[i] == -1:
				stack.append([i, c ^ 1])
				color[i] = c ^ 1
			elif color[i] != c ^ 1:
				print('NO')
				exit()

def main():
	(n, m) = mi()
	u = [0] * (m + 5)
	for i in range(m):
		(x, y) = mi()
		u[i] = x
		g[x].append(y)
		g[y].append(x)
	dfs(n)
	print('YES')
	for i in range(m):
		print(color[u[i]], end='')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
from collections import deque, Counter, OrderedDict, defaultdict
import threading
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[1]

def sort2(l):
	return sorted(l, key=getKey, reverse=True)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def ceil(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
g = defaultdict(list)
color = [-1] * 200005

def bfs(n):
	for i in range(n):
		if color[i] == -1:
			color[i] = 0
			Q = [(i, 0)]
			while Q:
				(node, c) = Q.pop()
				for nei in g[node]:
					if color[nei] == -1:
						color[nei] = 1 - c
						Q.append((nei, 1 - c))
					elif color[nei] != 1 - c:
						print('NO')
						exit()

def main():
	(n, m) = mi()
	u = [0] * 200005
	for i in range(m):
		(x, y) = mi()
		u[i] = x
		g[x].append(y)
		g[y].append(x)
	bfs(n)
	print('YES')
	for i in range(m):
		print(color[u[i]], end='')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
dmain()


from collections import deque

def solve():
	global n, m
	(n, m) = map(lambda x: int(x), input().split())
	global maxValue
	maxValue = n ** 2
	graph = [[] for _ in range(0, n)]
	edges = []
	for _ in range(0, m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		graph[u].append(v)
		graph[v].append(u)
		edges.append(v)
	distance = bfs_2k(graph, 0)
	if distance is None:
		print('NO')
	else:
		print('YES')
		print(''.join((str(distance[e] % 2) for e in edges)))

def bfs_2k(graph, initVertex):
	dist = [maxValue] * n
	queue = deque()
	queue.append(initVertex)
	dist[initVertex] = 0
	while queue:
		u = queue.popleft()
		for v in graph[u]:
			if dist[v] == maxValue:
				dist[v] = dist[u] + 1
				queue.append(v)
			elif (dist[u] - dist[v]) % 2 == 0:
				return None
	return dist
solve()


import sys
input = sys.stdin.readline
from collections import deque

class UnDirectedGraph:

	def __init__(self, N, M):
		self.V = N
		self.E = M
		self.edge = [[] for _ in range(self.V)]
		self.edges = [0] * self.E
		self.visited = [False] * self.V
		self.color = [-1] * self.V

	def add_edges(self, ind=1):
		for i in range(self.E):
			(a, b) = map(int, input().split())
			a -= ind
			b -= ind
			self.edge[a].append(b)
			self.edge[b].append(a)
			self.edges[i] = (a, b)

	def bfs(self, start):
		d = deque()
		self.color[start] = 0
		d.append(start)
		while len(d) > 0:
			v = d.popleft()
			for w in self.edge[v]:
				if self.color[w] == -1:
					self.color[w] = self.color[v] ^ 1
					d.append(w)
				elif self.color[w] == self.color[v]:
					return False
		return True
(N, M) = map(int, input().split())
G = UnDirectedGraph(N, M)
G.add_edges(1)
if G.bfs(0):
	print('YES')
	ans = ''
	for i in range(M):
		ans += str(G.color[G.edges[i][0]])
	print(ans)
else:
	print('NO')


from collections import deque

class Graph:

	def __init__(self, nvertices):
		self.nvertices = nvertices
		self.adj_list = [[] for v in range(nvertices + 1)]
		self.edges = []

	def add_edge(self, edge):
		self.edges.append(edge)

	def get_neighbors(self, ind):
		return self.adj_list[ind]

	def add_neighbor(self, vert, neighbor):
		self.adj_list[vert].append(neighbor)

	def print_graph(self):
		for (ind, vert) in enumerate(self.adj_list):
			if ind == 0:
				continue
			print(ind, '-->', vert)

def solve(graph):
	queue = set([(1, 0)])
	visited = [False] * (graph.nvertices + 1)
	marks = [None] * (graph.nvertices + 1)
	marks[1] = 0
	while len(queue):
		(vert, mark) = queue.pop()
		visited[vert] = True
		for neighbor in graph.get_neighbors(vert):
			if visited[neighbor] == False:
				queue.add((neighbor, not mark))
				marks[neighbor] = not mark
			elif marks[neighbor] == mark:
				print('NO')
				return
	print('YES')
	result = ''
	for (v1, v2) in graph.edges:
		if marks[v1] > marks[v2]:
			result += '0'
		else:
			result += '1'
	print(result)

def get_input():
	(nvertices, nedges) = list(map(int, input().split()))
	graph = Graph(nvertices)
	for edge in range(nedges):
		(v1, v2) = list(map(int, input().split()))
		graph.add_neighbor(v1, v2)
		graph.add_neighbor(v2, v1)
		graph.add_edge((v1, v2))
	return graph
graph = get_input()
solve(graph)


from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
	q = deque()
	q.append(s)
	dist = [-1] * (n + 1)
	dist[s] = 0
	ans = [0] * m
	while q:
		i = q.popleft()
		nd = dist[i] + 1
		for j in G[i]:
			if dist[j] == -1:
				dist[j] = nd
				q.append(j)
				if nd % 2:
					if (i, j) in d:
						ans[d[i, j]] = '1'
					else:
						ans[d[j, i]] = '0'
				elif (i, j) in d:
					ans[d[i, j]] = '0'
				else:
					ans[d[j, i]] = '1'
			else:
				if dist[j] % 2 ^ nd % 2:
					ans = 'NO'
					print(ans)
					exit()
				if nd % 2:
					if (i, j) in d:
						ans[d[i, j]] = '1'
					else:
						ans[d[j, i]] = '0'
				elif (i, j) in d:
					ans[d[i, j]] = '0'
				else:
					ans[d[j, i]] = '1'
	return ans
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
d = dict()
for i in range(m):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
	d[u, v] = i
ans = bfs(1)
print('YES')
print(''.join(ans))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

@iterative
def dfs(v, visited, frm, st, h, edges, dis):
	visited[st] = 1
	for i in v[st]:
		if i == frm:
			continue
		if visited[i] == 0:
			if h % 2:
				if (i, st) not in edges:
					edges[st, i] = 1
			elif (st, i) not in edges:
				edges[i, st] = 1
			dis[i] = h
			ok = (yield dfs(v, visited, st, i, h + 1, edges, dis))
		else:
			if h < dis[i]:
				continue
			if (h - dis[i]) % 2:
				global f
				f = -1
			elif (st, frm) in edges:
				if edges[st, frm] == 0:
					if (st, i) not in edges:
						edges[i, st] = 1
				elif (i, st) not in edges:
					edges[st, i] = 1
			elif edges[frm, st] == 0:
				if (i, st) not in edges:
					edges[st, i] = 1
			elif (st, i) not in edges:
				edges[i, st] = 1
	yield True

def solve(case):
	(n, m) = sep()
	g = [[] for i in range(n)]
	edges = {}
	for i in range(m):
		(x, y) = sep()
		x -= 1
		y -= 1
		edges[x, y] = 0
		g[x].append(y)
		g[y].append(x)
	vis = [0] * n
	dis = [0] * n
	dfs(g, vis, -1, 0, 1, edges, dis)
	global f
	if f == -1:
		print('NO')
		return
	print('YES')
	print(''.join((str(edges[i]) for i in edges)))
f = 1
testcase(1)


from collections import deque
from math import inf as infinity

def solve():
	global n, m
	(n, m) = map(lambda x: int(x), input().split())
	graph = [[] for _ in range(0, n)]
	edges = [-1] * m
	for i in range(0, m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		graph[u].append(v)
		graph[v].append(u)
		edges[i] = v
	distance = bfs_2k(graph, 0)
	if distance is None:
		print('NO')
	else:
		print('YES')
		print(''.join((str(distance[e] % 2) for e in edges)))

def bfs_2k(graph, s):
	dist = [infinity] * n
	queue = deque()
	queue.append(s)
	dist[s] = 0
	while queue:
		u = queue.popleft()
		for v in graph[u]:
			if dist[v] == infinity:
				dist[v] = dist[u] + 1
				queue.append(v)
			elif (dist[u] - dist[v]) % 2 == 0:
				return None
	return dist
solve()


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
edges = []
for i in range(m):
	(a, b) = map(int, input().split())
	edges.append((a - 1, b - 1))
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
color = [-1] * n
q = deque([(0, -1)])
color[0] = 1
g = 0
while q:
	(node, parent) = q.popleft()
	(c, p) = (1, 0)
	if color[node] == 1:
		(c, p) = (0, 1)
	for i in graph[node]:
		if i != parent and color[i] == -1:
			color[i] = c
			q.append((i, node))
		elif i != parent and color[i] == p:
			g = 1
			break
if g:
	print('NO')
else:
	print('YES')
	for i in edges:
		if color[i[0]] == 1:
			print(0, end='')
		else:
			print(1, end='')


from sys import stdin
from collections import deque
input = stdin.readline

def solve():
	visited = [False] * (n + 1)
	direction = [True] * (n + 1)
	visited[1] = True
	queue = deque()
	queue.append(1)
	while queue:
		node = queue.popleft()
		for neighbor in g[node]:
			if visited[neighbor]:
				if direction[node] == direction[neighbor]:
					print('NO')
					return
			else:
				visited[neighbor] = True
				direction[neighbor] = not direction[node]
				queue.append(neighbor)
	ans = []
	for (u, v) in a:
		ans.append(int(direction[u]))
	print('YES')
	print(*ans, sep='')
(n, m) = [int(x) for x in input().split()]
g = [[] for _ in range(n + 1)]
a = []
for _ in range(m):
	(u, v) = [int(x) for x in input().split()]
	g[u].append(v)
	g[v].append(u)
	a.append((u, v))
solve()


from collections import deque
(n, v) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
inv_ori = [False] * (n + 1)
edge_s = []
for i in range(v):
	(u1, u2) = map(int, input().split())
	graph[u1].append(u2)
	graph[u2].append(u1)
	edge_s.append(u1)
Q = deque()
Q.append(1)
while len(Q) > 0:
	cur = Q.popleft()
	visited[cur] = True
	curinv = inv_ori[cur]
	for nxt in graph[cur]:
		if visited[nxt]:
			if curinv == inv_ori[nxt]:
				print('NO')
				exit(0)
		else:
			Q.append(nxt)
			inv_ori[nxt] = not curinv
print('YES')
for e in edge_s:
	print(int(inv_ori[e]), end='')


arr = input()
(N, E) = [int(x) for x in arr.split(' ')]
edges = [[0] * 2 for _ in range(E)]
edge_list = [[] for _ in range(N + 1)]
ans = {}
for i in range(E):
	s = input()
	(u, v) = [int(x) for x in s.split(' ')]
	edges[i][0] = u
	edges[i][1] = v
	edge_list[u].append(v)
	edge_list[v].append(u)
stack = [1]
ans = [-1] * (N + 1)
ans[1] = 1
cur = 1
flag = 0
while stack:
	p = stack.pop()
	cur = ans[p]
	for num in edge_list[p]:
		if ans[num] == -1:
			stack.append(num)
			ans[num] = cur ^ 1
		elif ans[num] == cur:
			flag = 1
			print('NO')
			quit()
if flag == 1:
	print('NO')
else:
	print('YES')
	for i in range(E):
		u = edges[i][0]
		print(ans[u], end='')


(n, m) = map(int, input().split())
a = []
g = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g[x].append(y)
	g[y].append(x)
	a.append([x, y])
b = [-1] * n
b[0] = 0
que = [0]

def nibu(x):
	for i in g[x]:
		if b[i] != -1 and b[i] == b[x]:
			print('NO')
			exit()
		elif b[i] == -1:
			b[i] = b[x] ^ 1
			que.append(i)
while que:
	nibu(que.pop())
ans = []
for i in range(m):
	if b[a[i][0]] == 0:
		ans.append('0')
	else:
		ans.append('1')
print('YES')
print(''.join(ans))


from sys import *
setrecursionlimit(3000)
(v, e) = map(int, input().split())
V = []
for i in range(v):
	V.append([-1, []])
edges = []
for i in range(e):
	(a, b) = map(int, input().split())
	edges.append([a - 1, b - 1])
	V[a - 1][1].append(b - 1)
	V[b - 1][1].append(a - 1)
cand = [0]
p = 1
f = True
while cand:
	ncan = []
	for c in cand:
		if V[c][0] == p:
			f = False
			break
		V[c][0] = p ^ 1
		for d in V[c][1]:
			if V[d][0] == -1:
				ncan.append(d)
	if not f:
		break
	p ^= 1
	cand = ncan
if not f:
	print('NO')
else:
	ans = []
	for x in edges:
		ans += str(V[x[0]][0])
	print('YES')
	print(''.join(ans))


import sys
from collections import defaultdict, deque

def cycle(graph, start):
	vis = defaultdict(int)
	popped = defaultdict(int)
	q = deque()
	q.append(start)
	vis[start] = 1
	while q:
		a = q.popleft()
		popped[a] = 1
		for i in graph[a]:
			if vis[i] == 1:
				if popped[i] == 0:
					return True
			else:
				vis[i] = 1
				q.append(i)
	return False

def color(graph, start, edges):
	q = deque()
	q.append([start, '0'])
	vis = defaultdict(int)
	vis[start] = 1
	while q:
		(a, col) = q.popleft()
		if col == '0':
			col = '1'
		else:
			col = '0'
		for k in graph[a]:
			if vis[k] == 1:
				if edges[k, a] == col:
					return False
				elif edges[k, a] == 0:
					edges[a, k] = col
			else:
				vis[k] = 1
				edges[a, k] = col
				q.append([k, col])
	return True
(n, m) = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
edges = defaultdict(int)
mark = [[0, 0] for _ in range(m)]
for i in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	graph[u].append(v)
	graph[v].append(u)
	mark[i] = [u, v]
start = u
val = '0'
a = color(graph, start, edges)
if not a:
	print('NO')
	sys.exit()
ans = [0 for _ in range(m)]
for i in range(m):
	if edges[mark[i][0], mark[i][1]] != 0:
		ans[i] = edges[mark[i][0], mark[i][1]]
	elif edges[mark[i][1], mark[i][0]] == '1':
		ans[i] = '0'
	else:
		ans[i] = '1'
print('YES')
print(''.join((c for c in ans)))


from collections import deque

def dfs_2k(graph, initNode, visited, color):
	stack = deque()
	stack.append(initNode)
	color[initNode] = 0
	while stack:
		u = stack.pop()
		visited[u] = True
		for v in graph[u]:
			if color[v] == color[u]:
				return False
			if not visited[v]:
				color[v] = color[u] ^ 1
				stack.append(v)
	return True
(n, m) = input().split()
n = int(n)
m = int(m)
graph = []
edges = []
visited = [False] * n
color = [-1] * n
for i in range(0, n):
	graph.append([])
for i in range(0, m):
	(u, v) = input().split()
	u = int(u) - 1
	v = int(v) - 1
	edges.append(v)
	graph[u].append(v)
	graph[v].append(u)
if dfs_2k(graph, 0, visited, color):
	print('YES')
	print(''.join((str(color[e]) for e in edges)))
else:
	print('NO')


(n, m) = map(int, input().split())
rinsetu = [[] for i in range(n + 1)]
inputlist = []
edge = [-1 for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	inputlist.append([u, v])
	rinsetu[u].append(v)
	rinsetu[v].append(u)
flag = 1
queue = [1]
edge[1] = 1
while len(queue) > 0:
	now = queue.pop()
	for i in rinsetu[now]:
		if edge[i] == -1:
			queue.append(i)
		if edge[now] == 1:
			if edge[i] == 1:
				flag = 0
			else:
				edge[i] = 0
		elif edge[i] == 0:
			flag = 0
		else:
			edge[i] = 1
	if flag == 0:
		break
ans = ''
if flag == 0:
	print('NO')
else:
	print('YES')
	for i in range(m):
		ans += str(edge[inputlist[i][1]])
print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
from heapq import *
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():

	def dfs(x):
		stack = [x]
		v[x] = 1
		while stack:
			a = stack.pop()
			for i in d[a]:
				if v[i]:
					if color[i] == color[a]:
						pr('NO')
						exit()
				else:
					color[i] = color[a] ^ 1
					v[i] = 1
					stack.append(i)
	(n, m) = mp()
	d = defaultdict(list)
	l = []
	for i in range(m):
		(a, b) = mp()
		l.append([a, b])
		d[a].append(b)
		d[b].append(a)
	color = defaultdict(lambda : -1)
	color[1] = 0
	v = defaultdict(int)
	dfs(1)
	ans = []
	pr('YES')
	for i in l:
		(a, b) = i
		if color[a] == 0:
			ans.append('1')
		else:
			ans.append('0')
	print(*ans, sep='')
for _ in range(1):
	solve()


(n, m) = map(int, input().split())
clr = [-1 for i in range(0, n)]
eds = []

def dfs():
	cur = 0
	st = [-1 for i in range(0, n + 1)]
	st[cur] = 0
	cur += 1
	while cur > 0:
		v = st[cur - 1]
		cur -= 1
		for x in g[v]:
			if clr[x] != -1:
				if clr[x] == clr[v]:
					return False
				continue
			clr[x] = clr[v] ^ 1
			st[cur] = x
			cur += 1
	return True
g = [[] for i in range(0, n)]
for i in range(0, m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
	eds.append((u, v))
clr[0] = 0
if dfs():
	print('YES')
	print(''.join(('1' if clr[u] < clr[v] else '0' for (u, v) in eds)))
else:
	print('NO')


(n, m) = map(int, input().split(' '))
color = [-1 for i in range(n)]
neighbour = [[] for i in range(n)]
store = []
for i in range(m):
	(p, q) = map(int, input().split(' '))
	store.append([p - 1, q - 1])
	neighbour[p - 1].append(q - 1)
	neighbour[q - 1].append(p - 1)
ans = ''
flag = True
color[0] = 1
queue = []
queue.append(0)
while queue:
	u = queue.pop()
	for v in neighbour[u]:
		if color[v] == -1:
			color[v] = 1 - color[u]
			queue.append(v)
		elif color[v] == color[u]:
			print('NO')
			flag = False
			queue = []
			break
if flag:
	for i in store:
		if color[i[0]] == 1:
			ans += '1'
		else:
			ans += '0'
	print('YES')
	print(ans)


class UnionFind:

	def __init__(self, num_elements):
		self.parent = list(range(num_elements))
		self.rank = [1] * num_elements

	def union(self, a, b):
		par_a = self.find(a)
		par_b = self.find(b)
		if par_a == par_b:
			return
		if self.rank[par_a] > self.rank[par_b]:
			self.parent[par_b] = par_a
			self.rank[par_a] = self.rank[par_a] + self.rank[par_b]
		else:
			self.parent[par_a] = par_b
			self.rank[par_b] = self.rank[par_a] + self.rank[par_b]

	def find(self, a):
		if self.parent[a] == a:
			return a
		par_a = self.find(self.parent[a])
		curr_parent = self.parent[a]
		if par_a != curr_parent:
			self.rank[curr_parent] -= self.rank[a]
			self.parent[a] = par_a
		return par_a
(n, m) = map(int, input().split())
edges = [[] for i in range(n + 1)]
inp_edges = []
uf = UnionFind(n + 1)
for i in range(m):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	edges[v].append(u)
	inp_edges.append((u, v))
possible = True
for i in range(1, n + 1):
	if len(edges[i]):
		node_parent = uf.find(i)
		first_parent = uf.find(edges[i][0])
		if first_parent == uf.find(i):
			possible = False
			break
		for neb in edges[i][1:]:
			parent = uf.find(neb)
			if parent == node_parent:
				possible = False
				break
			uf.union(first_parent, parent)
	if not possible:
		break
if not possible:
	print('NO')
else:
	print('YES')
	for i in range(1, n + 1):
		if len(edges[i]):
			first_parent = uf.find(i)
			break
	ans = []
	for e in inp_edges:
		if uf.find(e[0]) == first_parent:
			ans.append('1')
		else:
			ans.append('0')
	print(''.join(ans))


(n, m) = map(int, input().split())
gr = [[] for i in range(n)]
trr = []
for i in range(m):
	(u, v) = map(int, input().split())
	gr[u - 1].append(v - 1)
	gr[v - 1].append(u - 1)
	trr.append(v)
tr = {}
for i in range(n):
	tr[i] = -1
tr[0] = 0
s = set([0])
v = [False for i in range(n)]
t = True
while s and t:
	x = s.pop()
	k = 1 if tr[x] == 0 else 0
	v[x] = True
	for j in gr[x]:
		if v[j]:
			if tr[j] == k:
				continue
			else:
				t = False
				break
		else:
			tr[j] = k
			s.add(j)
if t:
	print('YES')
	s = ''
	for i in trr:
		s += str(tr[i - 1])
	print(s)
	exit()
tr = {}
for i in range(n):
	tr[i] = -1
tr[0] = 1
s = set([0])
v = [False for i in range(n)]
t = True
while s and t:
	x = s.pop()
	k = 1 if tr[x] == 0 else 0
	v[x] = True
	for j in gr[x]:
		if v[j]:
			if tr[j] == k:
				continue
			else:
				t = False
				break
		else:
			tr[j] = k
			s.add(j)
if t:
	print('YES')
	s = ''
	for i in trr:
		s += str(tr[i - 1])
	print(s)
	exit()
print('NO')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
g = [[] for i in range(n)]
for (u, v) in edges:
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
c = [-1] * n
q = [0]
c[0] = 0
f = True
while q:
	ver = q.pop()
	for to in g[ver]:
		if c[to] == -1:
			c[to] = c[ver] ^ 1
			q.append(to)
		elif c[to] != 1 ^ c[ver]:
			f = False
			break
if not f:
	print('NO')
	exit()
ans = []
for (u, v) in edges:
	if c[u - 1] == 0:
		ans.append(0)
	else:
		ans.append(1)
print('YES')
print(''.join(map(str, ans)))


from collections import defaultdict

def main():
	(n, m) = map(int, input().split())
	roads = []
	graph = defaultdict(dict)
	for _ in range(m):
		(u, v) = map(int, input().split())
		roads.append((u, v))
		graph[u][v] = 1
		graph[v][u] = 1
	nodes = [-1 for _ in range(n + 1)]
	nodes[1] = 1
	stack = [1]
	while stack:
		cur = stack.pop()
		flag = nodes[cur]
		if flag:
			for i in graph[cur]:
				if graph[cur][i]:
					if nodes[i] == -1:
						nodes[i] = 0
						stack.append(i)
					elif nodes[i] == 1:
						return print('NO')
					graph[cur][i] = 0
					graph[i][cur] = 0
		else:
			for i in graph[cur]:
				if graph[cur][i]:
					if nodes[i] == -1:
						nodes[i] = 1
						stack.append(i)
					elif nodes[i] == 0:
						return print('NO')
					graph[cur][i] = 0
					graph[i][cur] = 0
	print('YES')
	out = ''
	for i in roads:
		if nodes[i[0]] == 1:
			out += '1'
		else:
			out += '0'
	return print(out)
main()


import math
from collections import deque

def main():
	(n, m) = map(int, input().split())
	g = [[] for _ in range(n)]
	edges = []
	for e in range(m):
		(a, b) = map(int, input().split())
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
		edges.append((a - 1, b - 1))
	used = [False] * n
	mark = [False] * n
	q = deque([])

	def bfs():
		node = 0
		used[node] = True
		mark[node] = True
		q.append(node)
		while q:
			node = q.popleft()
			for neigh in g[node]:
				if used[neigh]:
					if mark[neigh] == mark[node]:
						return False
				if not used[neigh]:
					used[neigh] = True
					mark[neigh] = not mark[node]
					q.append(neigh)
		return True
	res = bfs()
	if res:
		print('YES')
		print(''.join(map(lambda e: '1' if mark[e[0]] and (not mark[e[1]]) else '0', edges)))
	else:
		print('NO')
main()


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left

def dfs(x, c):
	global flag
	stack = deque([[x, c]])
	while stack:
		(x, c) = stack.pop()
		if l[x] == -1:
			l[x] = c
		elif l[x] != c:
			flag = 0
			return
		else:
			continue
		for i in graph[x]:
			if l[i] == -1:
				stack.append([i, c ^ 1])
				graph[i].remove(x)
			elif l[x] == l[i]:
				flag = 0
				return
(n, m) = map(int, input().split())
graph = {i: set() for i in range(1, n + 1)}
ed = []
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].add(b)
	graph[b].add(a)
	ed.append([a, b])
l = [-1 for i in range(n + 1)]
flag = 1
dfs(1, 0)
if flag == 0:
	print('NO')
else:
	print('YES')
	for (i, j) in ed:
		if l[i] == 0 and l[j] == 1:
			print('0', end='')
		else:
			print('1', end='')


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
y = lambda : map(lambda x: int(x) - 1, input().split())
(n, m) = y()
(c, d, o) = ([-1] * (n + 1), [[] for _ in range(n + 1)], [])
for _ in range(m + 1):
	(a, b) = y()
	_ = (d[a].append(b), d[b].append(a), o.append((a, b)))
(c[a], q) = (0, [a])
while q:
	v = q.pop()
	for e in d[v]:
		if c[e] < 0:
			(c[e], _) = (c[v] ^ 1, q.append(e))
		elif c[e] == c[v]:
			_ = (print('NO'), exit())
print('YES\n' + ''.join(map(str, [c[k[0]] for k in o])))


from collections import defaultdict, deque

def bfs():
	q = deque([1])
	color[1] = 1
	while q:
		v = q.popleft()
		for i in g[v]:
			if color[i] == 0:
				color[i] = -color[v]
				q.append(i)
			elif color[i] == color[v]:
				return False
	return True
(n, m) = map(int, input().split())
edges = []
g = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
	edges.append((u, v))
color = [0] * (n + 1)
r = bfs()
if r == False:
	print('NO')
	exit(0)
ans = []
for (u, v) in edges:
	if color[u] == 1 and color[v] == -1:
		ans.append('1')
	else:
		ans.append('0')
print('YES')
print(''.join(ans))


from sys import stdin, stdout
import sys
import math
from collections import defaultdict, deque
sys.setrecursionlimit(15000)

def check_intersection(set_a, set_b):
	for i in range(len(set_a)):
		if set_a[i] == 1 and set_b[i] == 1:
			return False
	return True

def check_bipartite(graph, set_a, set_b):
	visited = dict()
	for i in range(1, n + 1):
		visited[i] = False
	myq = deque()
	myq.append(1)
	set_a[1] = 1
	while len(myq) > 0:
		node = myq.popleft()
		visited[node] = True
		for i in graph[node]:
			if visited[i] == False:
				if set_a[node] == 1:
					set_b[i] = 1
				else:
					set_a[i] = 1
				if set_a[i] == 1 and set_b[i] == 1:
					return False
				myq.append(i)
	return True
(n, m) = list(map(int, stdin.readline().split()))
graph = defaultdict(list)
aux = []
for _ in range(m):
	(u, v) = list(map(int, stdin.readline().split()))
	graph[u].append(v)
	graph[v].append(u)
	aux.append([u, v])
set_a = [0] * (n + 1)
set_b = [0] * (n + 1)
if check_bipartite(graph, set_a, set_b):
	ans = []
	for i in aux:
		(u, v) = i
		if set_a[u] == 1:
			ans.append('0')
		else:
			ans.append('1')
	print('YES')
	for i in ans:
		stdout.write(i)
else:
	print('NO')


from collections import deque
import sys
input = sys.stdin.buffer.readline

def bfs():
	visited = [0 for i in range(n + 1)]
	queue = deque()
	queue.append(1)
	while queue:
		par = queue.popleft()
		if visited[par] == 1:
			continue
		visited[par] = 1
		for child in graph[par]:
			if visited[child[0]] == 0:
				if ans[child[0]] == ans[par]:
					return 0
				if child[2] == 1:
					if ans[par] == 0:
						answed[child[1]] = 0
					else:
						answed[child[1]] = 1
				elif ans[par] == 0:
					answed[child[1]] = 1
				else:
					answed[child[1]] = 0
				queue.append(child[0])
	return 1

def dfs():
	visited = [0 for i in range(n + 1)]
	global ans
	queue = deque()
	queue.append(1)
	while queue:
		q = queue.popleft()
		if visited[q] == 1:
			continue
		visited[q] = 1
		for child in graph[q]:
			if visited[child[0]] == 0:
				queue.append(child[0])
				ans[child[0]] = (ans[q] + 1) % 2
(n, m) = map(int, input().split())
graph = [[] for i in range(n + 1)]
graph_l = [[] for i in range(n + 1)]
stored = []
for i in range(m):
	(a, b) = map(int, input().split())
	stored.append([a, b])
	graph[a].append([b, i, 1])
	graph[b].append([a, i, 0])
ans = [0 for i in range(n + 1)]
dfs()
answed = [0 for i in range(m)]
if bfs():
	print('YES')
	for i in range(0, m):
		print(answed[i], end='')
else:
	print('NO')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys
import math
from math import gcd
import bisect
from collections import deque
(n, m) = map(int, input().split())
ed = []
g = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	ed.append((u, v))
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
v = [-1] * n
q = deque([0])
v[0] = True
f = 0
while q:
	s = q.pop()
	for i in g[s]:
		if v[i] == -1:
			v[i] = not v[s]
			q.append(i)
		elif v[i] == v[s]:
			f = 1
if f == 1:
	print('NO')
else:
	print('YES')
	print(''.join(('1' if v[ed[i][0] - 1] else '0' for i in range(m))))


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
(n, m) = map(int, input().split())
d = defaultdict(list)
edges = []
for _ in range(m):
	(u, v) = map(int, input().split())
	edges.append((u - 1, v - 1))
	d[u - 1].append(v - 1)
	d[v - 1].append(u - 1)
color = [-1] * n
color[0] = True
q = deque([0])
flag = True
while q:
	first = q.popleft()
	for i in d[first]:
		if color[i] == -1:
			q.append(i)
			color[i] = not color[first]
		elif color[first] == color[i]:
			flag = False
if flag:
	print('YES')
	print(''.join(('1' if color[edges[i][0]] else '0' for i in range(m))))
else:
	print('NO')


from collections import deque

def bpc(graph):
	q = deque()
	for u in range(len(graph)):
		if color[u] == -1:
			color[u] = 0
			q.append(u)
			while q:
				u = q.popleft()
				for v in graph[u]:
					if color[v] == -1:
						q.append(v)
						color[v] = 1 - color[u]
					elif color[v] == color[u]:
						return False
	return True
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
color = [-1 for _ in range(n)]
xy = []
for i in range(m):
	pair = list(map(lambda x: int(x) - 1, input().split()))
	xy += [pair]
	graph[pair[0]].append(pair[1])
	graph[pair[1]].append(pair[0])
if not bpc(graph):
	print('NO')
else:
	print('YES')
	for i in range(m):
		if color[xy[i][0]] == 0:
			print(1, end='')
		else:
			print(0, end='')


from collections import deque

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj_list = [[] for u in range(V + 1)]
		self.edges = []

	def add_edge(self, edge):
		self.edges.append(edge)

	def add_neighdor(self, v1, v2):
		self.adj_list[v1].append(v2)

	def get_neighdor(self, v):
		return self.adj_list[v]

def solve(graph):
	color = [0] * graph.V
	queue = [(0, 1)]
	color[0] = 1
	i = 0
	while i != len(queue):
		for v in graph.get_neighdor(queue[i][0]):
			if not color[v]:
				color[v] = 3 - queue[i][1]
				queue.append((v, color[v]))
		i += 1
	ans = ['0'] * len(graph.edges)
	for i in range(len(graph.edges)):
		if color[graph.edges[i][0]] == color[graph.edges[i][1]]:
			print('NO')
			return
		if color[graph.edges[i][0]] == 1:
			ans[i] = '1'
	print('YES')
	print(''.join(ans))

def get_input():
	(n, m) = map(int, input().split())
	graph = Graph(n)
	for _ in range(m):
		(v1, v2) = map(int, input().split())
		graph.add_neighdor(v1 - 1, v2 - 1)
		graph.add_neighdor(v2 - 1, v1 - 1)
		graph.add_edge((v1 - 1, v2 - 1))
	return graph
graph = get_input()
solve(graph)