有些题解够了，这题和三分图的判定没有什么关系……
这里主要是一个转化，一个点会和所以不与自己相连的点处于相同的集合中。
换句话说，如果两个点在同一个集合内，那与这两个点相连的点的集合是完全相同的。
这里使用了哈希来判定，另外，如果有孤立的点存在，则要特判。
const int maxN=1e5+10;
vector<int> g[maxN];
int n,m;
pll hsh[maxN];
int col[maxN];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=rd(),m=rd();
fp(i,1,m){
int u=rd(),v=rd();
g[u].eb(v),g[v].eb(u);
}
fp(i,1,n){
if(g[i].empty()){
cout << "-1" << endl;
return 0;
}
}
fp(i,1,n)
sort(g[i].begin(),g[i].end());
fp(i,1,n){
hsh[i].second=i;
for(int x:g[i])
hsh[i].first=(hsh[i].first*base+x)%mod;
}
sort(hsh+1,hsh+n+1);
vector<int> v;
fp(i,2,n)
if(hsh[i].first!=hsh[i-1].first) v.eb(i);
if(v.size()!=2){
cout << "-1" << endl;
return 0;
}
fp(i,1,v[0]-1)
col[hsh[i].second]=1;
fp(i,v[0],v[1]-1)
col[hsh[i].second]=2;
fp(i,v[1],n)
col[hsh[i].second]=3;
fp(i,1,n) cout << col[i] << ' ';
cout << endl;
return 0;
}