#include<bits/stdc++.h> using namespace std; #define N 300005 int n,m; vector<int>e[N]; int vis[N]; struct sset { int fa[N],rk[N]; void init(){ for(int i=1;i<=n;i++) fa[i]=i,rk[i]=1; } int find(int x){ if(fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x]; } bool merge(int x,int y){ x=find(x),y=find(y); if(x==y) return 0; if(rk[x]<rk[y]) swap(x,y); fa[y]=fa[x]; rk[x]+=rk[y]; return 1; } }s; int flood(int u,int id){ vis[u]=id; int sz=1; for(int v:e[u]){ if(vis[v]) continue; sz+=flood(v,id); } return sz; } void dfs(int u,int from){ vis[u]=1; for(int &v:e[u]){ if(v==from){ v=-1; continue; } if(vis[v]) continue; dfs(v,u); v=-1; } } void solve(){ cin>>n>>m; for(int i=1;i<=n;i++){ e[i].clear(); } for(int u,v,i=1;i<=m;i++){ cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } int cnt=0,id=-1,tmp[3]; for(int i=1;i<=n;i++) vis[i]=0; for(int i=1;i<=n;i++){ if(vis[i]) continue; tmp[cnt++]=i; if(flood(i,i)>1) id=i; if(cnt>=3) break; } if(cnt>=2){ if(cnt>=3){ // cout<<'!'<<endl; for(int i=1;i<=n;i++){ if(vis[i]==tmp[0]) cout<<1; else if(vis[i]==tmp[1]) cout<<2; else cout<<3; cout<<' '; } }else{ // cout<<'@'<<endl; for(int i=1;i<=n;i++){ if(i==id) cout<<1; else if(vis[i]==id) cout<<2; else cout<<3; cout<<' '; } } }else{ // cout<<'#'<<endl; for(int i=1;i<=n;i++) vis[i]=0; dfs(1,0); s.init(); for(int u=1;u<=n;u++){ for(int v:e[u]){ if(v==-1) continue; s.merge(u,v); } } tmp[0]=tmp[1]=tmp[2]=cnt=0; for(int i=1;i<=n;i++){ if(i==s.find(i)) tmp[cnt++]=i; if(cnt==3) break; } // cout<<tmp[0]<<' '<<tmp[1]<<' '<<tmp[2]<<endl; for(int i=1;i<=n;i++){ if(s.find(i)==tmp[0]) cout<<1; else if(s.find(i)==tmp[1]) cout<<2; else cout<<3; cout<<' '; } } cout<<endl; } int main(){ ios::sync_with_stdio(0); solve(); return 0; }