Graph and String

题意翻译

## 题意 给出一个由字符串$s$建图的过程。 - 字符仅有$a,b,c$三种，建出的图中第$i$个顶点表示原来的第$i$个字符。 - $i$与$j$有连边，当且仅当$s[i]$与$s[j]$相同或$s[i]$和$s[j]$是相邻的字符（$a$与$b$相邻，$b$与$c$相邻） 现给出由某个字符串$s$建出的图，构造一个字符串使其符合上面的要求要求，或者回答不存在这样的字符串。 ###### 输入： 第一行两个整数$n,m$，表示节点数（即字符串长度）和边数。 接下来$m$行，每行两个数字 $u_{i}$ 和 $v_{i}$，表示这两个节点之间有一条边。 ###### 输出： 如果字符串存在，第一行输出一个$“Yes”，第二行输出符合条件的字符串。 如果不存在，仅在第一行输出一个“No”。

题目描述

One day student Vasya was sitting on a lecture and mentioned a string $ s_{1}s_{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 $ .

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $  — 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.

输出格式

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.

输入输出样例

输入样例 #1

2 1
1 2

输出样例 #1

Yes
aa

输入样例 #2

4 3
1 2
1 3
1 4

输出样例 #2

No

说明

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.