CF623A Graph and String

有一天，学生 Vasya 在上课时发现他的桌子上写着一个由字母 "a"、"b" 和 "c" 组成的字符串 $s_1 s_2 \ldots s_n$。由于课堂无聊，Vasya 决定用这个字符串构造一张满足以下性质的图 $G$： - $G$ 恰好有 $n$ 个顶点，编号从 $1$ 到 $n$。 - 对于所有 $i \neq j$ 的顶点对，如果且仅如果 $s_i$ 和 $s_j$ 这两个字符相同，或者相邻（字母表中彼此相邻），则在顶点 $i$ 和 $j$ 之间连一条边。具体来说，"a" 和 "b" ，"b" 和 "c" 是相邻的，"a" 和 "c" 不是。 Vasya 在字符串旁边画好了这张图，然后把字符串擦掉了。第二天，Vasya 的朋友 Petya 来上课，发现桌子上有一张图。他听说了 Vasya 的事，现在他想知道这个图是否可能是 Vasya 按上述方式画出来的。如果可能，那么就要找出一种符合要求的字符串 $s$，能够使 Vasya 以此构造出此图。

输入的第一行包含两个整数 $n$ 和 $m$，表示 Petya 发现的图的顶点数和边数。 接下来的 $m$ 行中，每行包含两个整数 $u_i$ 和 $v_i$ $(1 \le u_i, v_i \le n, u_i \ne v_i)$，表示图 $G$ 中的一条无向边。保证没有重边，即任意一对顶点在列表中最多只出现一次。

如果存在 Petya 想要找的字符串 $s$，则第一行输出 "Yes"；否则输出 "No"。 如果字符串 $s$ 存在，第二行输出一个只包含 "a"、"b" 和 "c" 的、长度恰好为 $n$ 的字符串，使得按照题意用这个字符串构造出来的图与输入的图完全一致。如果有多种可能答案，可以输出任意一种。

在第一个样例中，给出的是一个包含两条顶点、相连的一条边的图。所以这两个顶点可以是相同的字母，也可以是相邻字母。如下字符串均满足条件："aa"、"ab"、"ba"、"bb"、"bc"、"cb"、"cc"。 在第二个样例中，第一个顶点与另外三个顶点都有边，但这三个顶点彼此之间没有边。这意味着这三个顶点应对应不同且互不相邻的字母，但由于只有 "a" 和 "c" 这两个字母是互不相邻的，这是不可能的。 由 ChatGPT 5 翻译