One day student Vasya was sitting on a lecture and mentioned a string s_1s_2... s_{n}, consisting of letters "a", "b" and "c" that was written on his desk. As the lecture was boring, Vasya decided to complete the picture by composing a graph G with the following properties:   G has exactly n vertices, numbered from 1 to n.  For all pairs of vertices i and j, where i ≠ j, there is an edge connecting them if and only if characters s_{i} and s_{j} are either equal or neighbouring in the alphabet. That is, letters in pairs "a"-"b" and "b"-"c" are neighbouring, while letters "a"-"c" are not. 

Vasya painted the resulting graph near the string and then erased the string. Next day Vasya's friend Petya came to a lecture and found some graph at his desk. He had heard of Vasya's adventure and now he wants to find out whether it could be the original graph G, painted by Vasya. In order to verify this, Petya needs to know whether there exists a string s, such that if Vasya used this s he would produce the given graph G.


-----Input-----

The first line of the input contains two integers n and m $(1 \leq n \leq 500,0 \leq m \leq \frac{n(n - 1)}{2})$ — the number of vertices and edges in the graph found by Petya, respectively.

Each of the next m lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the edges of the graph G. It is guaranteed, that there are no multiple edges, that is any pair of vertexes appear in this list no more than once.


-----Output-----

In the first line print "Yes" (without the quotes), if the string s Petya is interested in really exists and "No" (without the quotes) otherwise.

If the string s exists, then print it on the second line of the output. The length of s must be exactly n, it must consist of only letters "a", "b" and "c" only, and the graph built using this string must coincide with G. If there are multiple possible answers, you may print any of them.


-----Examples-----
Input
2 1
1 2

Output
Yes
aa

Input
4 3
1 2
1 3
1 4

Output
No



-----Note-----

In the first sample you are given a graph made of two vertices with an edge between them. So, these vertices can correspond to both the same and adjacent letters. Any of the following strings "aa", "ab", "ba", "bb", "bc", "cb", "cc" meets the graph's conditions. 

In the second sample the first vertex is connected to all three other vertices, but these three vertices are not connected with each other. That means that they must correspond to distinct letters that are not adjacent, but that is impossible as there are only two such letters: a and c.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms


Solutions:
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
connectionList = []
for _ in range(n):
	connectionList.append([0] * n)
for _ in range(m):
	(p, q) = map(int, input().split())
	connectionList[p - 1][q - 1] = 1
	connectionList[q - 1][p - 1] = 1
isDone = False
refList = []
ans = ['N'] * n
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		if connectionList[i][j] == 0:
			isDone = True
			refList = (i, j)
			ans[i] = 'a'
			ans[j] = 'c'
			break
	if isDone:
		break
if not isDone:
	print('Yes')
	print('a' * n)
else:
	isPossible = True
	for i in range(n):
		if i in refList:
			continue
		elif connectionList[i][refList[0]] == 1 and connectionList[i][refList[1]] == 1:
			ans[i] = 'b'
		elif connectionList[i][refList[0]] == 0 and connectionList[i][refList[1]] == 1:
			ans[i] = 'c'
		elif connectionList[i][refList[0]] == 1 and connectionList[i][refList[1]] == 0:
			ans[i] = 'a'
		else:
			isPossible = False
			break
	if not isPossible:
		print('No')
	else:
		isValid = True
		for i in range(n):
			for j in range(n):
				if i == j:
					continue
				if connectionList[i][j] == 0 and (ans[i] == 'a' and ans[j] == 'c' or (ans[j] == 'a' and ans[i] == 'c')):
					pass
				elif not connectionList[i][j] == 0 and (not (ans[i] == 'a' and ans[j] == 'c' or (ans[j] == 'a' and ans[i] == 'c'))):
					pass
				else:
					isValid = False
		if isValid:
			print('Yes')
			print(''.join(ans))
		else:
			print('No')


from pprint import pprint

def main():
	(n, m) = map(int, input().split(' '))
	adj = [[1] * n for _ in range(n)]
	for i in range(n):
		adj[i][i] = 0
	for _ in range(m):
		(x, y) = map(int, input().split(' '))
		x -= 1
		y -= 1
		adj[x][y] = adj[y][x] = 0
	adj = [tuple(r) for r in adj]
	reps = sorted({tuple([0] * n), *adj})
	if len(reps) == 1:
		print('Yes')
		print('a' * n)
		return
	elif len(reps) == 3:
		gs = [[0] * n for _ in range(3)]
		for (i, r) in enumerate(adj):
			ri = reps.index(r)
			gs[ri][i] = 1 if ri else 0
		gs = [tuple(g) for g in gs]
		for (i, r) in enumerate(adj):
			if r != gs[[0, 2, 1][reps.index(r)]]:
				print('No')
				return
		print('Yes')
		print(''.join(('bac'[reps.index(r)] for r in adj)))
		return
	print('No')
main()


def dfs(v, used, g):
	used[v] = True
	for x in g[v]:
		if not used[x]:
			dfs(x, used, g)
from collections import defaultdict, Counter
(n, m) = map(int, input().split())
g = defaultdict(set)
p = Counter()
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].add(b)
	g[b].add(a)
	p[a] += 1
	p[b] += 1
pows_set = defaultdict(set)
for i in range(n):
	pows_set[p[i]].add(i)
pows_list = list(pows_set.keys())
pows_list.sort()
if len(pows_list) > 3:
	print('No')
	exit()
if len(pows_list) == 3:
	flag = True
	for key in pows_set:
		for x in pows_set[key]:
			for y in pows_set[key]:
				if x != y and x not in g[y]:
					flag = False
	for x in pows_set[pows_list[-1]]:
		for i in range(n):
			if i != x and x not in g[i]:
				flag = False
	for x in pows_set[pows_list[0]]:
		for y in pows_set[pows_list[1]]:
			if x in g[y]:
				flag = False
	if not flag:
		print('No')
		exit()
	print('Yes')
	for i in range(n):
		if i in pows_set[pows_list[0]]:
			print('a', end='')
		if i in pows_set[pows_list[1]]:
			print('c', end='')
		if i in pows_set[pows_list[2]]:
			print('b', end='')
if len(pows_list) == 1:
	used = [False for i in range(n)]
	dfs(0, used, g)
	flag = True
	for i in range(n):
		for j in range(i + 1, n):
			if i == j:
				continue
			if used[i] == used[j] and i not in g[j]:
				flag = False
			if used[i] != used[j] and i in g[j]:
				flag = False
	if flag:
		print('Yes')
		for i in range(n):
			if used[i]:
				print('a', end='')
			else:
				print('c', end='')
	else:
		print('No')
if len(pows_list) == 2:
	used = [False for i in range(n)]
	dfs(0, used, g)
	flag = True
	for i in range(n):
		for j in range(i + 1, n):
			if used[i] == used[j] and i not in g[j]:
				flag = False
			if used[i] != used[j] and i in g[j]:
				flag = False
	if flag:
		print('Yes')
		for i in range(n):
			if used[i]:
				print('a', end='')
			else:
				print('c', end='')
		exit()
	flag = True
	for i in range(n):
		for j in range(n):
			if p[i] == p[j] and i not in g[j]:
				flag = False
			if p[i] != p[j] and i in g[j]:
				flag = False
	if flag:
		print('Yes')
		for i in range(n):
			if i in pows_set[pows_list[0]]:
				print('a', end='')
			else:
				print('b', end='')
		exit()
	flag = True
	for i in pows_set[pows_list[1]]:
		for j in range(n):
			if j in pows_set[pows_list[1]]:
				if i != j and i not in g[j]:
					flag = False
			elif i not in g[j]:
				flag = False
	new_g = defaultdict(set)
	for i in pows_set[pows_list[0]]:
		for x in g[i]:
			if x in pows_set[pows_list[0]]:
				new_g[i].add(x)
	used = dict()
	for x in pows_set[pows_list[0]]:
		used[x] = False
	dfs(list(pows_set[pows_list[0]])[0], used, new_g)
	for i in pows_set[pows_list[0]]:
		for j in pows_set[pows_list[0]]:
			if i == j:
				continue
			if used[i] == used[j] and i not in new_g[j]:
				flag = False
			if used[i] != used[j] and i in new_g[j]:
				flag = False
	if flag:
		print('Yes')
		for i in range(n):
			if i in pows_set[pows_list[0]]:
				if used[i]:
					print('a', end='')
				else:
					print('c', end='')
			else:
				print('b', end='')
	else:
		print('No')
exit()


(n, m) = [int(x) for x in input().split()]
E = {v: {v} for v in range(1, n + 1)}
for e in range(m):
	(u, v) = [int(x) for x in input().split()]
	E[u].add(v)
	E[v].add(u)
A = []
letter = [None for i in range(n)]
s = ''
k = iter('acx')
for v in E:
	for (i, p) in enumerate(A):
		if E[v] == p:
			letter[v - 1] = s[i]
			break
	else:
		if len(A) < 3:
			A.append(E[v])
			s = s + 'b' if len(E[v]) == n else s + next(k)
			if s[-1] == 'x':
				print('No')
				break
			letter[v - 1] = s[-1]
		else:
			print('No')
			break
else:
	print('Yes')
	print(''.join(letter))


from sys import exit

def dfs(node, letter):
	visited[node] = True
	ans[node - 1] = letter
	s.add(tuple(sorted(graph[node] + [node])))
	for adj in graph[node]:
		if not visited[adj]:
			dfs(adj, letter)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
visited = [False] * (n + 1)
ans = ['x' for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
	degree[a] += 1
	degree[b] += 1
for node in range(1, n + 1):
	if degree[node] == n - 1:
		visited[node] = True
		ans[node - 1] = 'b'
for letter in ['a', 'c']:
	for node in range(1, n + 1):
		if not visited[node]:
			s = set()
			dfs(node, letter)
			if len(s) > 1:
				print('No')
				exit(0)
			break
print('Yes\n' + ''.join(ans) if not False in visited[1:] else 'No')


(n, m) = map(int, input().split())
graph = [set() for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	graph[u].add(v)
	graph[v].add(u)
letter = {'a': set(), 'b': set(), 'c': set()}
for u in range(1, n + 1):
	if len(graph[u]) == n - 1:
		letter['b'].add(u)
inconsistent = False
for u in range(1, n + 1):
	if u in letter['b']:
		continue
	letter['a'].add(u)
	for v in range(1, n + 1):
		if u == v:
			continue
		elif v in letter['b']:
			continue
		elif v in graph[u]:
			letter['a'].add(v)
		else:
			letter['c'].add(v)
	break
for u in range(1, n + 1):
	if u in letter['b']:
		continue
	for v in range(u + 1, n + 1):
		if v in letter['b']:
			continue
		elif v in graph[u]:
			if (u in letter['a']) ^ (v in letter['a']):
				inconsistent = True
		elif not (u in letter['a']) ^ (v in letter['a']):
			inconsistent = True
res = list()
for u in range(1, n + 1):
	if u in letter['a']:
		res.append('a')
	elif u in letter['b']:
		res.append('b')
	elif u in letter['c']:
		res.append('c')
if inconsistent:
	print('No')
else:
	print('Yes')
	print(''.join(map(str, res)))


color = [-1] * 510
vis = [0] * 510

def dfs(start):
	vis[start] = 1
	for i in g[start]:
		if vis[i] == 0:
			color[i] = 1 - color[start]
			dfs(i)
		if vis[i] != 0:
			if color[i] == color[start]:
				print('No')
				quit()
g = {}
for i in range(510):
	g[i] = []
h = []
for i in range(510):
	h.append([0] * 510)
cosas = []
(a, b) = map(int, input().split(' '))
for c in range(b):
	(d, e) = map(int, input().split(' '))
	h[d][e] = 1
	h[e][d] = 1
	cosas.append([d, e])
for i in range(1, a + 1):
	for j in range(1, a + 1):
		if h[i][j] != 1 and i != j:
			g[i].append(j)
for i in range(1, a + 1):
	if len(g[i]) == 0:
		color[i] = -1
		vis[i] = 1
	if vis[i] == 0:
		color[i] = 0
		dfs(i)
estrenga = ''
for i in range(1, a + 1):
	if color[i] == 0:
		estrenga += 'a'
	elif color[i] == 1:
		estrenga += 'c'
	else:
		estrenga += 'b'
for i in cosas:
	arra = [i[0], i[1]]
	arrb = [estrenga[arra[0] - 1], estrenga[arra[1] - 1]]
	arrb.sort()
	if arrb[0] == 'a' and arrb[1] == 'c':
		print('No')
		quit()
print('Yes')
print(estrenga)


(n, m) = map(int, input().split())
s = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	s[a - 1][b - 1] = 1
	s[b - 1][a - 1] = 1
for i in range(n):
	s[i][i] = 1
answer = [0] * n
for i in range(n):
	flag = True
	for j in range(n):
		if s[i][j] == 0:
			flag = False
	if flag:
		answer[i] = 'b'
for i in range(n):
	if answer[i] == 0:
		answer[i] = 'a'
		for j in range(n):
			if s[i][j] == 0:
				answer[j] = 'c'
			if s[i][j] == 1 and answer[j] != 'b':
				answer[j] = 'a'
		break
flag = True
for i in range(n):
	for j in range(n):
		if s[i][j] == 1:
			if answer[i] == 'a' and answer[j] == 'c' or (answer[i] == 'c' and answer[j] == 'a'):
				flag = False
		if s[i][j] == 0:
			if abs(ord(answer[i]) - ord(answer[j])) < 2:
				flag = False
if flag:
	print('Yes')
	answer = ''.join(answer)
	print(answer)
else:
	print('No')


from sys import stdin

def YES(ans):
	(print('Yes'), print(''.join(ans)), exit(0))

def NO():
	(print('No'), exit(0))

def main():
	(n, m) = [int(t) for t in input().split()]
	tru = [[False for f in range(n)] for t in range(n)]
	data = stdin.readlines()
	for line in data:
		(l, r) = [int(t) for t in line.split()]
		tru[l - 1][r - 1] = True
		tru[r - 1][l - 1] = True
	ans = ['-' for t in range(n)]
	for i in range(n):
		if tru[i].count(True) == n - 1:
			ans[i] = 'b'
	if '-' in ans:
		idx = ans.index('-')
		ans[idx] = 'a'
		for i in range(n):
			if i != idx and ans[i] != 'b':
				ans[i] = 'a' if tru[i][idx] else 'c'
	else:
		YES(ans)
	for p1 in range(n):
		for p2 in range(p1 + 1, n):
			if (abs(ord(ans[p1]) - ord(ans[p2])) < 2) != tru[p1][p2]:
				NO()
	YES(ans)
main()


def bfs(k):
	fila = [k]
	flag = [0] * (n + 1)
	flag[k] = 1
	while len(fila) != 0:
		v = fila[0]
		mark[v] = mark[k]
		fila.pop(0)
		for i in g[v]:
			if flag[i] == 0 and mark[i] != 'b':
				fila.append(i)
				flag[i] = 1
(n, m) = [int(x) for x in input().split()]
g = [[] for i in range(n + 1)]
res = 1
for i in range(m):
	(u, v) = [int(x) for x in input().split()]
	g[u].append(v)
	g[v].append(u)
deg = [0] * (n + 1)
mark = [0] * (n + 1)
contb = 0
for i in range(n + 1):
	deg[i] = len(g[i])
	if deg[i] == n - 1:
		mark[i] = 'b'
		contb += 1
for i in range(1, n + 1):
	if mark[i] == 0:
		mark[i] = 'a'
		bfs(i)
		break
for i in range(1, n + 1):
	if mark[i] == 0:
		mark[i] = 'c'
		bfs(i)
		break
conta = 0
contc = 0
for i in mark:
	if i == 'a':
		conta += 1
for i in mark:
	if i == 'c':
		contc += 1
for i in range(1, n + 1):
	if mark[i] == 'a' and deg[i] != conta - 1 + contb:
		res = 0
	if mark[i] == 'c' and deg[i] != contc - 1 + contb:
		res = 0
	if mark[i] == 0:
		res = 0
if res == 0:
	print('No')
else:
	mark.pop(0)
	r = ''.join(mark)
	print('Yes')
	print(r)


Read = lambda : map(int, input().split())
from functools import reduce

def init():
	g = [[False] * (n + 1) for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = Read()
		g[x][y] = g[y][x] = True
	return g

def solve():
	if n == 1 and m == 0:
		return 'Yes\n' + 'a'
	color = [0 for _ in range(n + 1)]
	g = init()
	for i in range(1, n + 1):
		if reduce(lambda x, y: x and y, g[i][1:i] + g[i][i + 1:]):
			color[i] = 2
	for u in range(1, n + 1):
		if not color[u]:
			color[u] = 1
			for v in range(1, n + 1):
				if u != v and g[u][v] and (not color[v]):
					color[v] = 1
			break
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if i == j:
				continue
			if g[i][j] and color[i] + color[j] == 1:
				return 'No'
			if not g[i][j] and color[i] == color[j]:
				return 'No'

	def judge(x):
		if x == 1:
			return 'a'
		elif x == 2:
			return 'b'
		else:
			return 'c'
	return 'Yes\n' + ''.join(map(judge, color[1:]))
while True:
	try:
		(n, m) = Read()
	except:
		break
	print(solve())


(n, m) = [int(x) for x in input().split()]
connections = [[i != j for j in range(n)] for i in range(n)]
cnt = [0] * n
for _ in range(m):
	(u, v) = [int(x) - 1 for x in input().split()]
	connections[u][v] = connections[v][u] = False
	cnt[u] += 1
	cnt[v] += 1
s = [''] * n
for (i, c) in enumerate(cnt):
	if c == n - 1:
		s[i] = 'b'

def traverse(vertex, letter):
	s[vertex] = letter
	for (i, connection) in enumerate(connections[vertex]):
		if connection:
			if s[i] == '':
				if not traverse(i, 'c' if letter == 'a' else 'a'):
					return False
			elif s[i] == letter:
				return False
	return True
possibility = True
for i in range(n):
	if s[i] == '':
		possibility = traverse(i, 'a')
		break
for (i, c) in enumerate(s):
	for j in range(n):
		if connections[i][j] != (s[i] == 'a' and s[j] == 'c' or (s[i] == 'c' and s[j] == 'a')):
			possibility = False
			break
if possibility:
	print('Yes', ''.join(s), sep='\n')
else:
	print('No')


(n, m) = map(int, input().split())
v = [[0] * n for i in range(n)]
ans = ['$'] * n
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	v[x][y] = 1
	v[y][x] = 1
for i in range(n):
	v[i][i] = 1
for i in range(n):
	deg = 0
	for j in range(n):
		deg += v[i][j]
	if deg == n:
		ans[i] = 'b'
for i in range(n):
	if ans[i] != 'b':
		for j in range(n):
			if v[i][j] and ans[j] != 'b':
				ans[j] = 'a'
		break
for i in range(n):
	if ans[i] != 'b' and ans[i] != 'a':
		for j in range(n):
			if v[i][j] and ans[j] != 'b':
				ans[j] = 'c'
		break
w = [[abs(ord(ans[i]) - ord(ans[j])) <= 1 for j in range(n)] for i in range(n)]
if w == v and ans.count('$') == 0:
	print('Yes', ''.join(ans), sep='\n')
else:
	print('No')


class StdIO:

	def read_int(self):
		return int(self.read_string())

	def read_ints(self, sep=None):
		return [int(i) for i in self.read_strings(sep)]

	def read_float(self):
		return float(self.read_string())

	def read_floats(self, sep=None):
		return [float(i) for i in self.read_strings(sep)]

	def read_string(self):
		return input()

	def read_strings(self, sep=None):
		return self.read_string().split(sep)
io = StdIO()

def dfs(adj, visited, v, word, c, component):
	visited[v] = True
	word[v] = c
	component.append(v)
	for u in adj[v]:
		if not visited[u]:
			dfs(adj, visited, u, word, c, component)

def main():
	(n, m) = io.read_ints()
	adj = [list() for i in range(n)]
	for i in range(m):
		(u, v) = io.read_ints()
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	word = [None] * n
	visited = [False] * n
	bs = 0
	for v in range(n):
		if len(adj[v]) == n - 1:
			visited[v] = True
			word[v] = 'b'
			bs += 1
	comp = 0
	good = True
	for v in range(n):
		if not visited[v]:
			comp += 1
			if comp > 2:
				good = False
				break
			component = []
			dfs(adj, visited, v, word, ['a', 'c'][comp - 1], component)
			size = len(component)
			good = True
			for u in component:
				if len(adj[u]) != size - 1 + bs:
					good = False
					break
			if not good:
				break
	if not good:
		print('No')
		return
	print('Yes')
	print(''.join(word))
main()


from collections import defaultdict
import queue

class GraphString:

	def __init__(self, n, m, edges):
		self.edge_list = defaultdict(list)
		self.nonedge_list = defaultdict(list)
		for (x, y) in edges:
			self.edge_list[x - 1].append(y - 1)
			self.edge_list[y - 1].append(x - 1)
		for i in range(n):
			self.nonedge_list[i] = list(set(range(n)) - set([i] + self.edge_list[i]))

	def is_possible(self):
		check = [-1] * n
		count = [0] * n
		is_consistent = True
		for i in range(n):
			if check[i] == -1:
				q = queue.Queue(maxsize=n)
				check[i] = 0
				q.put(i)
				while not q.empty():
					v = q.get()
					count[i] += 1
					for nv in self.nonedge_list[v]:
						if check[nv] == check[v]:
							is_consistent = False
						elif check[nv] == -1:
							check[nv] = (check[v] + 1) % 2
							q.put(nv)
				if count[i] == 1:
					check[i] = 2
		if not is_consistent or len(list(filter(lambda x: x > 1, count))) > 1:
			print('No')
		else:
			n0 = len(list(filter(lambda x: x == 0, check)))
			n1 = len(list(filter(lambda x: x == 1, check)))
			edge_count = 0
			for i in range(n):
				if check[i] in [0, 1]:
					edge_count += len(self.nonedge_list[i])
			if edge_count != 2 * n0 * n1:
				print('No')
			else:
				print('Yes')
				chars = ['a', 'c', 'b']
				for i in range(n):
					check[i] = chars[check[i]]
				print(''.join(check))
(n, m) = list(map(int, input().strip(' ').split(' ')))
edges = []
for i in range(m):
	(x, y) = list(map(int, input().strip(' ').split(' ')))
	edges.append((x, y))
graph = GraphString(n, m, edges)
graph.is_possible()


(n, m) = input().split()
n = int(n)
m = int(m)
a = n * [False]
for i in range(0, n):
	a[i] = n * [False]
s = n * ['0']
adj = n * [0]
for i in range(0, m):
	(u, v) = input().split()
	u = int(u) - 1
	v = int(v) - 1
	a[u][v] = True
	a[v][u] = True
	adj[u] += 1
	adj[v] += 1

def dfs(u):
	global res
	if adj[u] == n - 1:
		s[u] = 'b'
		return
	if s[u] == 'a':
		change = 'c'
	else:
		change = 'a'
		s[u] = 'c'
	for i in range(0, n):
		if not a[u][i] and i != u:
			if s[i] == s[u]:
				res = 'No'
				return
			else:
				s[i] = change
		elif i != u and s[i] == change:
			res = 'No'
res = 'Yes'
for i in range(0, n):
	if res == 'Yes':
		dfs(i)
print(res)
if res == 'Yes':
	for i in s:
		print(i, end='')


(n, m) = tuple(map(int, input().split()))
cnt = [0] * n
edges = []
for i in range(m):
	(u, v) = tuple(map(int, input().split()))
	edges.append((u, v))
	cnt[u - 1] += 1
	cnt[v - 1] += 1
edge_set = set(edges)
A = set()
B = set()
C = set()
for i in range(n):
	if cnt[i] == n - 1:
		B.add(i + 1)
	else:
		in_A = True
		in_C = True
		for a in A:
			if (a, i + 1) not in edge_set and (i + 1, a) not in edge_set:
				in_A = False
			else:
				in_C = False
		for c in C:
			if (c, i + 1) not in edge_set and (i + 1, c) not in edge_set:
				in_C = False
			else:
				in_A = False
		if in_A == True and in_C == True:
			A.add(i + 1)
		elif in_A == False and in_C == True:
			C.add(i + 1)
		elif in_A == True and in_C == False:
			A.add(i + 1)
		else:
			print('No')
			break
else:
	print('Yes')
	ans = ''
	for i in range(1, n + 1):
		if i in A:
			ans += 'a'
		if i in B:
			ans += 'b'
		if i in C:
			ans += 'c'
	print(ans)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, M, edges):
	if M == N * (N - 1) // 2:
		return 'a' * N
	g = collections.defaultdict(list)
	for (u, v) in edges:
		g[u].append(v)
		g[v].append(u)
	s = ['', 'a', 'b', 'c']
	for u in range(1, N + 1):
		mark = [3 for _ in range(N + 1)]
		mark[0] = 0
		mark[u] = 1
		for v in g[u]:
			mark[v] = 1
		for u in range(1, N + 1):
			if mark[u] == 3:
				for v in g[u]:
					if mark[v] == 1:
						mark[v] = 2
		(a, b, c) = (mark.count(1), mark.count(2), mark.count(3))
		if a * (a - 1) // 2 + b * (b - 1) // 2 + c * (c - 1) // 2 + a * b + b * c != M:
			continue
		if any([abs(mark[u] - mark[v]) > 1 for (u, v) in edges]):
			continue
		return ''.join([s[mark[v]] for v in range(1, N + 1)])
	return None
(N, M) = map(int, input().split())
edges = []
for i in range(M):
	(u, v) = map(int, input().split())
	edges.append((u, v))
s = solve(N, M, edges)
if s:
	print('Yes')
	print(s)
else:
	print('No')


from sys import stdin
(n, m) = [int(x) for x in stdin.readline().split()]
graph = [set([y for y in range(n)]) for x in range(n)]
graph2 = [set() for x in range(n)]
for x in range(n):
	graph[x].remove(x)
for edge in range(m):
	(a, b) = [int(x) for x in stdin.readline().split()]
	a -= 1
	b -= 1
	graph[a].remove(b)
	graph[b].remove(a)
	graph2[a].add(b)
	graph2[b].add(a)
notVisited = set([x for x in range(n)])
val = [-1 for x in range(n)]
for x in range(n):
	if not graph[x]:
		val[x] = 'b'
		notVisited.remove(x)
valid = True
while notVisited:
	for x in notVisited:
		q = [(x, 'a')]
		break
	cur = 0
	while q:
		(nxt, char) = q.pop()
		if char == 'a':
			antC = 'c'
		else:
			antC = 'a'
		if nxt in notVisited:
			notVisited.remove(nxt)
			val[nxt] = char
			for x in graph[nxt]:
				if x in notVisited:
					q.append((x, antC))
				elif val[x] == char:
					valid = False
					break
			for x in graph2[nxt]:
				if val[x] == antC:
					valid = False
if valid:
	print('Yes')
	print(''.join(val))
else:
	print('No')


edge = [[0 for _ in range(510)] for _ in range(510)]
cnt = [0] * 510
s = [0] * 510
(n, m) = map(int, input().split())
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	edge[u][v] = 1
	edge[v][u] = 1
	cnt[u] += 1
	cnt[v] += 1
for i in range(n):
	if cnt[i] == n - 1:
		s[i] = 'b'
for i in range(n):
	if s[i] == 0:
		s[i] = 'a'
		for j in range(n):
			if s[j] == 0:
				if edge[i][j] != 0:
					s[j] = 'a'
				else:
					s[j] = 'c'
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		if abs(ord(s[i]) - ord(s[j]) == 2 and edge[i][j] == 1) or (abs(ord(s[i]) - ord(s[j])) < 2 and edge[i][j] == 0):
			print('No')
			exit()
print('Yes')
print(''.join(s[:s.index(0)]))


from queue import Queue
from sys import stdin

def YES():
	(print('Yes'), print(''.join(ans)), exit(0))

def NO():
	(print('No'), exit(0))
(n, m) = [int(t) for t in input().split()]
tru = [[False for f in range(n)] for t in range(n)]
lst = [list() for t in range(n)]
for _ in range(m):
	(l, r) = [int(t) for t in stdin.readline().split()]
	lst[l - 1].append(r - 1)
	lst[r - 1].append(l - 1)
	tru[l - 1][r - 1] = True
	tru[r - 1][l - 1] = True
ans = ['-' for t in range(n)]
for i in range(len(lst)):
	if len(lst[i]) == n - 1:
		ans[i] = 'b'
if '-' in ans:
	idx = ans.index('-')
	ans[idx] = 'a'
	for i in range(n):
		if i != idx and ans[i] != 'b':
			ans[i] = 'a' if tru[i][idx] else 'c'
else:
	YES()
for p1 in range(n):
	for p2 in range(p1 + 1, n):
		if (abs(ord(ans[p1]) - ord(ans[p2])) < 2) != tru[p1][p2]:
			NO()
YES()


def build(n, m):
	g = [[0 for i in range(n)] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split(' '))
		g[v - 1][u - 1] = 1
		g[u - 1][v - 1] = 1
	return g

def dfs(v, c):
	cnt = 0
	for i in range(n):
		if v != i and g[v][i] == 0:
			cnt += 1
	if cnt != 0:
		used[v] = 1
		ans[v] = c
		for i in range(n):
			if not used[i] and g[v][i] == 0:
				cTo = 'a'
				if c == 'a':
					cTo = 'c'
				dfs(i, cTo)

def check():
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if g[i][j] == 1:
				if ans[i] == 'a' and ans[j] == 'c':
					return False
				if ans[i] == 'c' and ans[j] == 'a':
					return False
			else:
				if ans[i] == ans[j]:
					return False
				if ans[i] == 'a' and ans[j] == 'b':
					return False
				if ans[i] == 'b' and ans[j] == 'a':
					return False
				if ans[i] == 'b' and ans[j] == 'c':
					return False
				if ans[i] == 'c' and ans[j] == 'b':
					return False
	return True
(n, m) = map(int, input().split())
used = [0 for i in range(n)]
ans = ['b' for i in range(n)]
g = build(n, m)
for i in range(n):
	if not used[i]:
		dfs(i, 'a')
if check() == True:
	print('Yes')
	for i in range(n):
		print(ans[i], end='')
else:
	print('No')


def dfs(v):
	visit[v] = cnt
	for u in vertex[v]:
		if not visit[u] and u in challengers:
			dfs(u)
(n, m) = map(int, input().split())
vertex = [[] for i in range(n + 1)]
challengers = set()
ans = [''] * (n + 1)
middle = set()
for i in range(m):
	(a, b) = map(int, input().split())
	vertex[a].append(b)
	vertex[b].append(a)
for i in range(1, n + 1):
	s = set((j for j in range(1, n + 1)))
	s.discard(i)
	if s == set(vertex[i]):
		ans[i] = 'b'
		middle.add(i)
	else:
		challengers.add(i)
visit = [0] * (n + 1)
cnt = 0
for c in challengers:
	if not visit[c]:
		cnt += 1
		dfs(c)
if cnt > 2 or cnt == 1:
	print('No')
elif cnt == 2:
	first = set()
	second = set()
	for i in range(1, n + 1):
		if visit[i] == 1:
			first.add(i)
		elif visit[i] == 2:
			second.add(i)
	for c in first:
		s = first
		s.discard(c)
		if set(vertex[c]) - middle != s:
			print('No')
			break
		s.add(c)
	else:
		for c in first:
			ans[c] = 'a'
		for c in second:
			s = second
			s.discard(c)
			if set(vertex[c]) - middle != s:
				print('No')
				break
			s.add(c)
		else:
			for c in second:
				ans[c] = 'c'
if not ans[1:].count(''):
	print('Yes', ''.join(ans[1:]), sep='\n')


import sys
(n, m) = map(int, input().split())
graph = [set([i]) for i in range(n)]
for i in range(m):
	(i, j) = map(int, input().split())
	graph[i - 1].add(j - 1)
	graph[j - 1].add(i - 1)
thebs = set()
for i in range(n):
	if len(graph[i]) == n:
		thebs.add(i)
aset = False
cset = False
theas = set()
thecs = set()
flag = True
for i in range(n):
	if i in thebs:
		pass
	elif aset == False:
		aset = graph[i]
		theas.add(i)
	elif graph[i] == aset:
		theas.add(i)
	elif cset == False:
		cset = graph[i]
		thecs.add(i)
	elif graph[i] == cset:
		thecs.add(i)
	else:
		print('No')
		flag = False
		break
if flag:
	print('Yes')
	for i in range(n):
		if i in theas:
			print('a', end='')
		elif i in thebs:
			print('b', end='')
		elif i in thecs:
			print('c', end='')


(n, m) = map(int, input().split())
connectionList = []
for _ in range(n):
	connectionList.append([0] * n)
for _ in range(m):
	(p, q) = map(int, input().split())
	connectionList[p - 1][q - 1] = 1
	connectionList[q - 1][p - 1] = 1
isDone = False
refList = []
ans = ['N'] * n
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		if connectionList[i][j] == 0:
			isDone = True
			refList = (i, j)
			ans[i] = 'a'
			ans[j] = 'c'
			break
	if isDone:
		break
if not isDone:
	print('Yes')
	print('a' * n)
else:
	isPossible = True
	for i in range(n):
		if i in refList:
			continue
		elif connectionList[i][refList[0]] == 1 and connectionList[i][refList[1]] == 1:
			ans[i] = 'b'
		elif connectionList[i][refList[0]] == 0 and connectionList[i][refList[1]] == 1:
			ans[i] = 'c'
		elif connectionList[i][refList[0]] == 1 and connectionList[i][refList[1]] == 0:
			ans[i] = 'a'
		else:
			isPossible = False
			break
	if not isPossible:
		print('No')
	else:
		isValid = True
		for i in range(n):
			for j in range(n):
				if i == j:
					continue
				if connectionList[i][j] == 0 and (ans[i] == 'a' and ans[j] == 'c' or (ans[j] == 'a' and ans[i] == 'c')):
					pass
				elif not connectionList[i][j] == 0 and (not (ans[i] == 'a' and ans[j] == 'c' or (ans[j] == 'a' and ans[i] == 'c'))):
					pass
				else:
					isValid = False
		if isValid:
			print('Yes')
			print(''.join(ans))
		else:
			print('No')


def main():
	(n, m) = map(int, input().split())
	g = [[0] * n for i in range(n)]
	for i in range(m):
		(x, y) = map(int, input().split())
		g[x - 1][y - 1] = 1
		g[y - 1][x - 1] = 1
	(a, c) = (-1, -1)
	for i in range(n):
		for j in range(i + 1, n):
			if g[i][j] == 0:
				(a, c) = (i, j)
	if (a, c) == (-1, -1):
		print('Yes')
		print('a' * n)
		return
	ans = ['x'] * n
	ans[a] = 'a'
	ans[c] = 'c'
	for i in range(n):
		if i != a and i != c:
			if g[i][a] + g[i][c] == 2:
				ans[i] = 'b'
			elif g[i][a] == 1:
				ans[i] = 'a'
			else:
				ans[i] = 'c'
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if g[i][j] == 0 and (ans[i] + ans[j] != 'ac' and ans[i] + ans[j] != 'ca'):
				print('No')
				return
			if g[i][j] == 1 and (ans[i] + ans[j] == 'ac' or ans[i] + ans[j] == 'ca'):
				print('No')
				return
	print('Yes')
	print(''.join(ans))
main()


from collections import defaultdict, deque, Counter, OrderedDict
import sys
sys.setrecursionlimit(20000)

def main():
	(n, m) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		adj[a].append(b)
		adj[b].append(a)
	ans = ['c'] * n
	visited = [0] * n
	for i in range(n):
		if len(adj[i]) == n - 1:
			visited[i] = 1
			ans[i] = 'b'

	def dfs(s, c):
		if visited[s]:
			return
		(visited[s], ans[s]) = (1, c)
		for j in adj[s]:
			dfs(j, c)
	if 'c' in ans:
		st = ans.index('c')
		dfs(st, 'a')
	if 'c' in ans:
		st = ans.index('c')
		dfs(st, 'c')
	(check, cnta, cntc, cntb) = (True, ans.count('a'), ans.count('c'), ans.count('b'))
	for i in range(n):
		if ans[i] == 'a':
			check &= len(adj[i]) == cnta + cntb - 1
		elif ans[i] == 'c':
			check &= len(adj[i]) == cntc + cntb - 1
	if check:
		print('Yes\n' + ''.join(ans))
	else:
		print('No')
main()


def main():
	(n, m) = map(int, input().split())
	links = [[False] * n for i in range(n)]
	for i in range(n):
		links[i][i] = True
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		links[u][v] = links[v][u] = True
	res = [0] * n
	ref1 = ref3 = None
	for (i, link) in enumerate(links):
		if all(link):
			res[i] = 2
	if not all(res):
		i = res.index(0)
		res[i] = 1
		ref1 = links[i]
		for (i, f) in enumerate(ref1):
			if f and (not res[i]):
				res[i] = 1
		if not all(res):
			i = res.index(0)
			res[i] = 3
			ref3 = links[i]
			for (i, f) in enumerate(ref3):
				if f:
					mark = res[i]
					if mark == 1:
						print('No')
						return
					if not mark:
						res[i] = 3
	ref = [None, ref1, None, ref3]
	for (i, mark) in enumerate(res):
		if not mark:
			print('No')
			return
		if mark & 1:
			if ref[mark] != links[i]:
				print('No')
				return
	print('Yes')
	print(''.join((' abc'[mark] for mark in res)))
main()


import collections
(n, m) = map(int, input().split())
(ans, A, B, C) = ([''] * n, [], [], [])
d = collections.defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().split())
	d[y - 1].append(x - 1)
	d[x - 1].append(y - 1)
for (k, v) in d.items():
	if len(v) == n - 1:
		ans[k] = 'b'
		B.append(k)
for i in range(n):
	if ans[i] == '':
		ans[i] = 'a'
		A.append(i)
		de = collections.deque()
		de.append(i)
		while len(de) != 0:
			cur = de.popleft()
			for j in d[cur]:
				if ans[j] == '':
					ans[j] = 'a'
					A.append(j)
					de.append(j)
		break
for i in range(n):
	if ans[i] == '':
		ans[i] = 'c'
		C.append(i)
temp = sorted(A + B)
for i in A:
	d[i].append(i)
	if sorted(d[i]) != temp:
		print('No')
		exit(0)
temp = sorted(B + C)
for i in C:
	d[i].append(i)
	if sorted(d[i]) != temp:
		print('No')
		exit(0)
print('Yes')
print(''.join(ans))


import sys
(V, E) = map(int, input().split(' '))
neighbours = [set() for x in range(V)]
for i in range(E):
	(v1, v2) = map(int, input().split(' '))
	neighbours[v1 - 1].add(v2 - 1)
	neighbours[v2 - 1].add(v1 - 1)
mapping = ['?'] * V
for v in range(V):
	if len(neighbours[v]) == V - 1:
		mapping[v] = 'b'
for v in range(V):
	if mapping[v] == 'b':
		for n in neighbours[v]:
			neighbours[n].remove(v)
neighbours = list(map(list, neighbours))
stack = next(([v] for v in range(V) if mapping[v] == '?'), [])
if stack != []:
	mapping[stack[0]] = 'a'
while stack != []:
	top = stack.pop()
	for n in neighbours[top]:
		if mapping[n] == '?':
			mapping[n] = 'a'
			stack.append(n)
for v in range(V):
	if mapping[v] == '?':
		mapping[v] = 'c'
counts = {'a': mapping.count('a'), 'c': mapping.count('c')}
for v in range(V):
	if mapping[v] != 'b' and len(neighbours[v]) != counts[mapping[v]] - 1:
		print('No')
		sys.exit()
print('Yes')
print(''.join(mapping))


(n, m) = (int(_) for _ in input().split())
e = [set() for i in range(n + 1)]
deg = [0 for i in range(n + 1)]
for i in range(m):
	(x, y) = (int(_) for _ in input().split())
	deg[x] += 1
	deg[y] += 1
	e[x].add(y)
	e[y].add(x)
s = ['' for i in range(n + 1)]
ans = 2
for i in range(1, n + 1):
	if deg[i] == n - 1:
		s[i] = 'b'
for i in range(1, n + 1):
	if deg[i] != n - 1 and s[i] == '':
		s[i] = 'a' if ans == 2 else 'c'
		if ans == 2:
			for j in e[i]:
				if s[j] == '':
					s[j] = 'a'
		elif ans == 1:
			for j in e[i]:
				if s[j] == 'a':
					ans = -1
				elif s[j] == '':
					s[j] = 'c'
		ans -= 1
for i in s[1:]:
	if i == '':
		ans = -1
if ans >= 0:
	for i in range(1, n + 1):
		for j in range(1 + i, n + 1):
			if s[i] == 'a' and s[j] == 'c' or (s[i] == 'c' and s[j] == 'a'):
				if i in e[j] or j in e[i]:
					ans = -1
			elif j not in e[i] or i not in e[j]:
				ans = -1
if ans >= 0:
	print('Yes')
	print(''.join(s[1:]))
else:
	print('No')


f = lambda : map(int, input().split())
(n, m) = f()
p = [1 << i for i in range(n)]
for i in range(m):
	(x, y) = f()
	x -= 1
	y -= 1
	p[x] |= 1 << y
	p[y] |= 1 << x
s = set(p)
b = (1 << n) - 1
t = {}
if b in s:
	t[b] = 'b'
	s.remove(b)
if len(s) == 2:
	(a, c) = s
	if a | c == b and bool(a & c) == (b in t):
		(t[a], t[c]) = 'ac'
		s.clear()
print('No' if s else 'Yes\n' + ''.join(map(t.get, p)))


(n, m) = map(int, input().split(' '))
G = [[0] * n for i in range(n)]
for i in range(m):
	(u, v) = map(lambda x: int(x) - 1, input().split(' '))
	G[u][v] = G[v][u] = 1
s = [' '] * n
for i in range(n):
	if G[i].count(1) == n - 1:
		s[i] = 'b'
try:
	anode = s.index(' ')
	s[anode] = 'a'
except:
	print('Yes')
	print(''.join(s))
	exit()
for i in range(n):
	if s[i] == ' ' and G[anode][i] == 1:
		s[i] = 'a'
	elif s[i] == ' ' and G[anode][i] == 0:
		s[i] = 'c'
for i in range(n):
	for j in range(i + 1, n):
		if (s[i] != s[j] and s[i] != 'b' and (s[j] != 'b')) == G[i][j]:
			print('No')
			exit()
print('Yes')
print(''.join(s))


from string import ascii_lowercase

def indx(c):
	global ascii_lowercase
	return ascii_lowercase.index(c)

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

def new_list(n):
	return [0 for i in range(n)]

def new_matrix(n, m=0):
	return [[0 for i in range(m)] for i in range(n)]
(n, m) = read_list()
n += 1
string = new_list(n)
v = new_matrix(n, n)
for i in range(m):
	(v1, v2) = read_list()
	v[v1][v2] = True
	v[v2][v1] = True
for i in range(1, n):
	l = v[i].count(True)
	if l == n - 2:
		string[i] = 'b'
for i in range(1, n):
	if string[i]:
		continue
	string[i] = 'a'
	for j in range(1, n):
		if string[j]:
			continue
		if v[i][j] == True:
			string[i] = 'a'
		else:
			string[i] = 'c'
for i in range(1, n):
	for j in range(1, n):
		if i == j:
			continue
		if abs(indx(string[i]) - indx(string[j])) == 2 and v[i][j] or (abs(indx(string[i]) - indx(string[j])) < 2 and (not v[i][j])):
			print('No')
			exit()
print('Yes')
for i in range(1, n):
	print(string[i], end='')
print()


import copy
(n, m) = [int(x) for x in input().split()]
res = []
for i in range(n):
	d = [0] * n
	d[i] = 1
	res.append(d)
for i in range(m):
	(r, c) = [int(x) for x in input().split()]
	res[r - 1][c - 1] = 1
	res[c - 1][r - 1] = 1
groups = ['x'] * n
cor1 = []
cor2 = []
output = ''
for i in range(n):
	if res[i] == [1] * n:
		groups[i] = 'b'
for i in range(n):
	if not groups[i] == 'b':
		if len(cor1) == 0:
			cor1 = copy.deepcopy(res[i])
			groups[i] = 'a'
		elif res[i] == cor1:
			groups[i] = 'a'
		elif len(cor2) == 0:
			cor2 = copy.deepcopy(res[i])
			groups[i] = 'c'
		elif res[i] == cor2:
			groups[i] = 'c'
		else:
			output = 'No'
			break
if len(output) == 0:
	print('Yes')
	print(''.join(groups))
else:
	print('No')


def dfs(v, graph, used, str_arr, color=0):
	used[v] = True
	str_arr[v] = color
	for u in graph[v]:
		if used[u] and str_arr[u] == color:
			return False
		if not used[u] and (not dfs(u, graph, used, str_arr, color ^ 1)):
			return False
	return True

def main():
	(n, m) = list(map(int, input().strip().split()))
	graph_adj = [[0] * n for i in range(n)]
	for i in range(m):
		(a, b) = list(map(int, input().strip().split()))
		a -= 1
		b -= 1
		graph_adj[a][b] = 1
		graph_adj[b][a] = 1
	arr_adj = [[] for i in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			if graph_adj[i][j] == 0:
				arr_adj[i].append(j)
				arr_adj[j].append(i)
	used = [False] * n
	str_arr = [-1] * n
	for i in range(n):
		if not used[i] and len(arr_adj[i]) > 0:
			if not dfs(i, arr_adj, used, str_arr):
				print('No')
				return
	for i in range(n):
		if str_arr[i] == -1:
			str_arr[i] = 'b'
		elif str_arr[i] == 0:
			str_arr[i] = 'a'
		else:
			str_arr[i] = 'c'
	for i in range(n):
		for j in range(i + 1, n):
			if graph_adj[i][j] and (str_arr[i] == 'a' and str_arr[j] == 'c' or (str_arr[i] == 'c' and str_arr[j] == 'a')):
				print('No')
				return
	print('Yes')
	print(''.join(str_arr))
main()


from math import *
(N, M) = (510, 3 * 10 ** 5 + 10)
g = [[] for _ in range(M)]
(n, m) = map(int, input().split())
mx = [[False] * N for _ in range(N + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	mx[u][v] = mx[v][u] = True
all_eq = True
mark = [False] * N
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if not mx[i][j]:
			all_eq = False
			mark[i] = True
			g[i].append(j)
			g[j].append(i)
if all_eq:
	print('YES')
	print(n * 'a')
	exit(0)
ans = [-1] * N

def dfs(v, c):
	ans[v] = c
	res = False
	for u in g[v]:
		if ans[u] == -1:
			res |= dfs(u, 2 - c)
		elif ans[u] == ans[v]:
			return False
	return res
for i in range(1, n + 1):
	if mark[i] and ans[i] == -1 and dfs(i, 0):
		print('NO')
		exit(0)
for i in range(1, n + 1):
	if len(g[i]) == 0:
		ans[i] = 1
	if ans[i] == -1:
		print('NO')
		exit(0)
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if mx[i][j] != (abs(ans[i] - ans[j]) != 2):
			print('NO')
			exit(0)
print('YES')
for i in range(1, n + 1):
	print(chr(ans[i] + ord('a')), end='')
print()


R = lambda : map(int, input().split())
(n, m) = R()
graph = [set() for _ in range(n)]
for i in range(m):
	(u, v) = R()
	graph[u - 1].add(v - 1)
	graph[v - 1].add(u - 1)
l = [-1] * n
for i in range(n):
	if len(graph[i]) == n - 1:
		l[i] = 1
for i in range(n):
	if l[i] == -1:
		l[i] = 0
		for j in range(n):
			if j in graph[i] and l[j] != 1:
				l[j] = 0
		break
for i in range(n):
	if l[i] == -1:
		l[i] = 2
for i in range(n):
	for j in range(i + 1, n):
		if l[i] == -1 or l[j] == -1:
			print('No')
			exit()
		elif l[i] == 1 or l[j] == 1:
			if j not in graph[i]:
				print('No')
				exit()
		elif l[i] == l[j]:
			if j not in graph[i]:
				print('No')
				exit()
		elif l[i] != l[j]:
			if j in graph[i]:
				print('No')
				exit()
res = ''
for i in range(n):
	if l[i] == 0:
		res += 'a'
	elif l[i] == 1:
		res += 'b'
	else:
		res += 'c'
print('Yes')
print(res)


from collections import defaultdict
(n, m) = map(int, input('').split())
edge_list = defaultdict(list)
for i in range(m):
	(start, end) = map(int, input('').split())
	edge_list[start].append(end)
	edge_list[end].append(start)
set_b = set()
for vertice in edge_list:
	if len(edge_list[vertice]) == n - 1:
		set_b.add(vertice)
a_ver = None
for vertice in edge_list:
	if vertice not in set_b:
		a_ver = vertice
		break

def dfs(vertice, visited, set_a, set_b):
	if vertice in visited:
		return
	if vertice in set_b:
		return
	else:
		visited.add(vertice)
		set_a.add(vertice)
		for child in edge_list[vertice]:
			if child not in visited:
				dfs(child, visited, set_a, set_b)

def is_connected(set_type, connected_set):
	for vertice in set_type:
		for connected_vertice in connected_set:
			if connected_vertice != vertice and connected_vertice not in edge_list[vertice]:
				return False
	return True
if a_ver:
	visited = set()
	set_a = set()
	dfs(a_ver, visited, set_a, set_b)
	set_c = set((i for i in range(1, n + 1))) - set_b - set_a
	is_connected_a = is_connected(set_a, set_a.union(set_b))
	is_connected_c = is_connected(set_c, set_c.union(set_b))
	if is_connected_a and is_connected_c:
		constructed_string = ['a' if i in set_a else 'c' if i in set_c else 'b' for i in range(1, n + 1)]
		print('Yes')
		print(''.join(map(str, constructed_string)))
	else:
		print('No')
elif len(set_b) == n:
	constructed_string = ['a' for i in range(n)]
	print('Yes')
	print(''.join(map(str, constructed_string)))
elif n == 1:
	print('Yes')
	print('a')
elif n == 2:
	print('Yes')
	print('ac')
else:
	print('No')


(n, m) = map(int, input().split())
g = [set() for i in range(n)]
for i in range(m):
	a = tuple(map(int, input().split()))
	g[a[0] - 1].add(a[1] - 1)
	g[a[1] - 1].add(a[0] - 1)
res = [''] * n
good = 1
for i in range(n):
	if len(g[i]) == n - 1:
		res[i] = 'b'
a = 0
c = 0
for i in range(n):
	if a and res[i] == '':
		res[i] = 'c'
	if not a and res[i] == '':
		a = 1
		res[i] = 'a'
	if res[i] == 'a':
		for elem in g[i]:
			if res[elem] == 'c':
				good = 0
			if res[elem] == '':
				res[elem] = 'a'
	if res[i] == 'c':
		for elem in g[i]:
			if res[elem] == 'a':
				good = 0
			if res[elem] == '':
				res[elem] = 'c'
if '' in res:
	good = 0
for i in range(n):
	for j in range(i + 1, n):
		if res[j] == res[i]:
			if j not in g[i]:
				good = 0
if good:
	print('YES')
	print(''.join(res))
else:
	print('NO')


from collections import defaultdict as ddict
MAX_N = 1000
uni = [0] * MAX_N
graph = ddict(set)

def init(n):
	for i in range(n):
		uni[i] = -1

def root(x):
	if uni[x] < 0:
		return x
	else:
		uni[x] = root(uni[x])
		return uni[x]

def same(x, y):
	return root(x) == root(y)

def unite(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		return
	if uni[x] > uni[y]:
		(x, y) = (y, x)
	uni[x] += uni[y]
	uni[y] = x

def nC2(n):
	return n * (n - 1) // 2
(N, M) = map(int, input().split())
init(N)
for i in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	if u > v:
		(u, v) = (v, u)
	graph[u].add(v)
	graph[v].add(u)
b = set()
for i in range(N):
	if len(graph[i]) == N - 1:
		b.add(i)
for i in range(N):
	for j in graph[i]:
		if not i in b and (not j in b):
			unite(i, j)
cnt = 0
flag = True
parent = 0
for r in range(N):
	if not r in b and uni[r] < 0:
		if cnt >= 2:
			flag = False
			break
		for i in range(N):
			if same(i, r) and len(graph[i] - b) != -uni[r] - 1:
				flag = False
				break
		if not flag:
			break
		cnt += 1
		parent = r
if flag:
	print('Yes')
	s = ''
	for i in range(N):
		if i in b:
			s += 'b'
		elif same(i, parent):
			s += 'a'
		else:
			s += 'c'
	print(s)
else:
	print('No')