#include<bits/stdc++.h> #define int long long using namespace std; const int N=3e5+7; int n,m; vector<int> E[N]; bool vis[N]; vector<int> Comp[N]; int CC; int f[N]; inline void DFS(int u,int lst){ vis[u]=1;f[u]=lst;Comp[CC].push_back(u); for(auto v:E[u])if(!vis[v])DFS(v,u); } int Ans[N]; int D[N]; inline void Init(){for(int i=1;i<=n;i++)D[i]=i;} inline int Find(int x){return x==D[x]?x:D[x]=Find(D[x]);} inline void Merge(int u,int v){ u=Find(u),v=Find(v); D[u]=v; } vector<int> Col[N]; vector<int> VV[4]; inline void slv(){ cin>>n>>m; CC=0; VV[1].clear(),VV[2].clear(),VV[3].clear(); for(int i=1;i<=n;i++)Col[i].clear(),vis[i]=0,Comp[i].clear(),Ans[i]=f[i]=0,E[i].clear(); for(int i=1;i<=m;i++){ int u,v;cin>>u>>v; E[u].push_back(v),E[v].push_back(u); } for(int i=1;i<=n;i++)if(!vis[i])++CC,DFS(i,0); // for(int i=1;i<=n;i++)cout<<f[i]<<" "; // cout<<endl; if(CC>=2){ Ans[Comp[1][0]]=1; Ans[Comp[2][0]]=2; for(int i=1;i<=CC;i++){ for(int j=(i<=2);j<Comp[i].size();j++)Ans[Comp[i][j]]=3; } for(int i=1;i<=n;i++)VV[Ans[i]].push_back(i); // for(int i=1;i<=3;i++){ // cout<<VV[i].size()<<endl; // for(auto x:VV[i])cout<<x<<" "; // cout<<endl; // } for(int i=1;i<=n;i++)cout<<Ans[i]<<" "; cout<<endl; return; } Init(); for(int i=1;i<=n;i++){ for(auto v:E[i]){ if(f[v]!=i&&f[i]!=v){ Merge(i,v); // cout<<i<<" "<<v<<endl; } } } for(int i=1;i<=n;i++){ Col[Find(i)].push_back(i); } // for(int i=1;i<=n;i++){ // for(auto x:Col[i])cout<<x<<" "; // cout<<endl; // } int P=1; for(int i=1;i<=n;i++){ if(Col[i].size()){ for(auto x:Col[i])VV[P].push_back(x),Ans[x]=P; if(P<3)P++; } } // for(int i=1;i<=3;i++){ // cout<<VV[i].size()<<endl; // for(auto x:VV[i])cout<<x<<" "; // cout<<endl; // } // cout<<endl; for(int i=1;i<=n;i++)cout<<Ans[i]<<" "; cout<<endl; } signed main(){ #ifndef ONLINE_JUDGE freopen("nolife.in","r",stdin); freopen("nolife.out","w",stdout); #endif // int T;cin>>T; // while(T--)slv(); slv();return 0; }