不妨设 $1$ 号点在集合 $1$ 里
那么对于其他点，有且只有所有和 $1$ 没有边的点都在集合 $1$ 里
考虑不在集合 $1$ 的任意一个点 $x$ ，不妨设它在集合 $2$ 里
那么所有不在集合 $1$ 的，和 $x$ 没有边的点都在集合 $2$ 里，剩下的点都一定在集合 $3$ 里
所以集合划分完毕，然后就是判断合法性了，特判当然是越多越好啦！
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
}
const int N=6e5+7;
int n,m,bel[N],cnt[4];
int fir[N],from[N<<1],to[N<<1],cntt;
inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; }
int fa[N];
inline int find(int x) { return x!=fa[x] ? fa[x]=find(fa[x]) : x; }
int main()
{
n=read(),m=read(); int a,b;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
a=read(),b=read();
add(a,b); add(b,a); fa[find(a)]=find(b);
}
bel[1]=1; cnt[1]++;
for(int i=2;i<=n;i++)
{
bool GG=0;
for(int j=fir[i];j;j=from[j])
{
int &v=to[j]; if(v==1) GG=1;
}
if(!GG&&!bel[i]) bel[i]=1,cnt[1]++;
}
int x=0;
for(int i=fir[1];i;i=from[i])
{
x=to[i]; break;
}
bel[x]=2; cnt[2]++;
for(int i=1;i<=n;i++)
{
bool GG=0; if(bel[i]) continue;
for(int j=fir[i];j;j=from[j])
{
int &v=to[j]; if(v==x) GG=1;
}
if(!GG) bel[i]=2,cnt[2]++;
else bel[i]=3,cnt[3]++;
}
for(int i=1;i<=3;i++) if(!cnt[i]) { printf("-1\n"); return 0; }
if(cnt[1]*cnt[2]+cnt[2]*cnt[3]+cnt[1]*cnt[3]!=m) { printf("-1\n"); return 0; }
for(int i=1;i<=n;i++)
{
if(find(i)!=find(1)) { printf("-1\n"); return 0; }
int tot=0,res=0; if(!bel[i]) { printf("-1\n"); return 0; }
for(int j=fir[i];j;j=from[j])
{
int &v=to[j]; if(bel[v]==bel[i]) { printf("-1\n"); return 0; }
tot++;
}
for(int j=1;j<=3;j++) if(bel[i]!=j) res+=cnt[j];
if(tot!=res) { printf("-1\n"); return 0; }
}
for(int i=1;i<=n;i++) printf("%d ",bel[i]);
puts(""); return 0;
}