CF623A.Graph and String

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.

一天，学生瓦夏在听讲座时注意到课桌上写着一个由字母“a”、“b”和“c”组成的字符串 $s_1s_2\ldots s_n$。由于讲座枯燥乏味，瓦夏决定通过构造一个图 $G$ 来补全这个画面，该图需满足以下性质：

• $G$ 恰好有 $n$ 个顶点，编号从 $1$ 到 $n$；
• 对于所有顶点对 $i$ 和 $j$（其中 $i \ne j$），当且仅当字符 $s_i$ 与 $s_j$ 相等或在字母表中相邻时，顶点 $i$ 与 $j$ 之间存在一条边。即，“a”与“b”、“b”与“c”是相邻字母，而“a”与“c”不相邻。

瓦夏将所得的图画在字符串旁边，随后擦除了该字符串。第二天，瓦夏的朋友佩佳来上课时，在课桌上发现了一张图。他听说过瓦夏的这次尝试，现在他想弄清楚这张图是否有可能就是瓦夏当初所画的原始图 $G$。为了验证这一点，佩佳需要判断：是否存在某个字符串 $s$，使得若瓦夏使用该字符串 $s$，则恰好能生成给定的图 $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.

输入的第一行包含两个整数 $n$ 和 $m$ — 分别表示 Petya 找到的图中的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 ≤ u_i, v_i ≤ n$, $u_i ≠ v_i$）— 表示图 $G$ 的边。保证图中不存在重边，即任意一对顶点在该列表中至多出现一次。

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.

第一行输出“Yes”（不带引号），如果佩蒂亚感兴趣的字符串 $s$ 确实存在；否则输出“No”（不带引号）。

如果字符串 $s$ 存在，则在输出的第二行打印该字符串。字符串 $s$ 的长度必须恰好为 $n$，且仅由字母 “a”、“b” 和 “c” 组成；并且使用该字符串所构建的图必须与图 $G$ 完全一致。若存在多个可能的答案，可输出其中任意一个。

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.

在第一个样例中，给定一个由两个顶点及它们之间的一条边构成的图。因此，这两个顶点可以对应相同或相邻的字母。以下任意字符串“aa”、“ab”、“ba”、“bb”、“bc”、“cb”、“cc”均满足该图的条件。

在第二个样例中，第一个顶点与其余三个顶点均相连，但其余三个顶点彼此之间没有边相连。这意味着它们必须对应互不相同且两两不相邻的字母；然而这是不可能的，因为仅有两个这样的字母：a 和 c。