二分图染色
b点跟除自身外所有的点连接，共n-1个，首先把连接n-1个的点全部设为b点，其它点任意一点设为a，与a相连的都是a点，剩余为c点。最后验证是否成立。
验证条件为，所有连接的点之间的差值的绝对值不超过1，未连接的点之间的差值的绝对值都大于1.
#include<bits/stdc++.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
int mp[][];
int cnt[];
int flag[];
int n,m;
int main()
{
scanf("%d%d",&n,&m); for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=mp[y][x]=;
cnt[x]++;
cnt[y]++;
}
for(int i=;i<=n;i++)
{
if(cnt[i]==n-)
flag[i]=; }
int now=;
for(int i=;i<=n;i++)
{
if(flag[i]!=)
{
now=i;
break;
}
}
if(now==)
{
printf("Yes\n");
for(int i=;i<=n;i++)
printf("b");
return ;
} flag[now]=;
for(int i=;i<=n;i++)
{
if(now==i) continue;
// if(mp[i][now])
if(!mp[i][now]) flag[i]=;
else if(flag[i]==) flag[i]=;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(i==j) continue;
if(mp[i][j])
{
if(abs(flag[i]-flag[j])>)
return puts("No");
}
else
{
if(abs(flag[i]-flag[j])<=)
return puts("No");
}
}
}
printf("Yes\n");
for(int i=;i<=n;i++)
{
if(flag[i]==) cout<<'a';
else if(flag[i]==) cout<<'b';
else cout<<'c';
}
return ; }