← 返回题目列表

Codeforces · 623/A

A. 图形和字符串

中文机器翻译题面 查看原题

有一天,学生 Vasya 坐在课堂上,提到了写在他桌子上的字符串 s1s2...sn,由字母“a”、“b”和“c”组成。由于讲座很无聊,Vasya 决定通过构建具有以下属性的图 G 来完成图画:

- G 恰好有 n 个顶点,编号从 1 到 n。
- 对于所有顶点对 i 和 j,其中 i ≠ j,当且仅当字符 si 和 sj 在字母表中相等或相邻时,有一条边连接它们。也就是说,“a”-“b”和“b”-“c”对中的字母是相邻的,而字母“a”-“c”则不是。

Vasya 在字符串附近绘制了生成的图形,然后擦除了该字符串。第二天,瓦夏的朋友佩蒂亚来听讲座,在他的办公桌上发现了一些图表。他听说过瓦夏的冒险,现在他想知道这是否是瓦夏绘制的原始图形G。为了验证这一点,Petya 需要知道是否存在字符串 s,这样如果 Vasya 使用这个 s,他就会生成给定的图 G。

输入

输入的第一行包含两个整数 n 和 m $$( 1 \leq n \leq 500, 0 \leq m \leq \frac { n ( n - 1 ) } { 2 } )$$ — 分别是 Petya 找到的图中的顶点数和边数。

接下来的 m 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 图 G 的边。保证不存在多重边,即任何一对顶点在此列表中出现不超过一次。

输出

如果 Petya 感兴趣的字符串确实存在,则在第一行打印“Yes”(不带引号),否则打印“No”(不带引号)。

如果字符串 s 存在,则将其打印在输出的第二行。 s 的长度必须恰好为 n,它必须仅由字母“a”、“b”和“c”组成,并且使用该字符串构建的图形必须与 G 一致。如果有多个可能的答案,则可以打印其中任何一个。

示例

输入 #1

2 1
1 2

输出 #1

Yes
aa

输入 #2

4 3
1 2
1 3
1 4

输出 #2

No

注意

在第一个示例中,您会得到一个由两个顶点组成的图,两个顶点之间有一条边。因此,这些顶点可以对应于相同且相邻的字母。以下任何字符串“aa”、“ab”、“ba”、“bb”、“bc”、“cb”、“cc”都满足图形的条件。

在第二个示例中,第一个顶点连接到所有其他三个顶点,但这三个顶点未相互连接。这意味着它们必须对应于不相邻的不同字母,但这是不可能的,因为只有两个这样的字母:a 和 c。