Submission #68552307

---

Source Code Expand

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[205];
	#define gc() (p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++)
	#define flush() (fwrite(b,1,t-b,stdout),t=b)
	#define pc(x) (*t++=x,(t-b==sz)?flush():nullptr)
	template<class T> inline void read(T &x){
		x=0; char c=gc(),fushu=0;
		while(!isdigit(c)){if(c=='-')fushu=1; c=gc();}
		while(isdigit(c))x=x*10+(c^48),c=gc();
		if(fushu) x=-x;
	}
	inline void read(char &x){
		x=gc();
		while(!isgraph(x))x=gc();
	}
	inline void read(char *x){
		char c=gc();
		while(!isgraph(c))c=gc();
		while(isgraph(c))*x++=c,c=gc();
		*x='\0';
	}
	inline void read(string &x){
		x=""; char c=gc();
		while(!isgraph(c))c=gc();
		while(isgraph(c))x.push_back(c),c=gc();
	}
	template <typename T,typename ...Args> inline void read(T &x,Args &...args) { read(x),read(args...); }
	template<class T> inline void write(T x){
		if(x<0)pc('-'),x=-x;
		if(!x)pc('0');
		int l=0;
		while(x)p[++l]=(x%10)^48,x/=10;
		while(l)pc(p[l--]);
	}
	inline void write(char &x){pc(x);}
	inline void write(const char &x){pc(x);}
	inline void write(char *x){while(*x!='\0')pc(*x++);}
	inline void write(const char *x){while(*x!='\0')pc(*x++);}
	inline void write(string &x){for(auto c:x)pc(c);}
	template <typename T,typename ...Args> inline void write(T x,Args ...args) { write(x),write(args...); }
	struct F{~F(){flush();}}f;
	#undef gc
	#undef flush
	#undef pc
};
using IO::read;
using IO::write;
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define frein(name) freopen(name".in","r",stdin)
#define freout(name) freopen(name".out","w",stdout)
#define usefile(name) frein(name),freout(name)
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define fd(i,r,l) for(int i=(r);i>=(l);--i)
#define ll long long
#define ull unsigned long long
#define ld long double
#define it128 __int128
#define pi pair<int,int>
#define pl pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vp vector<pi>
#define Size(x) ((int)x.size())
const int N=2e5+5;
int n,m;
vi g[N];
vp e[N];
int vis[N],dep[N],fa[N][18],dfn[N],dn;
void dfs(int x,int y) {
	dfn[x]=++dn;
	dep[x]=dep[y]+1,vis[x]=1,fa[x][0]=y;
	fo(i,1,17) fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int v:g[x]) if(!vis[v]) dfs(v,x);
}
int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=dep[x]-dep[y],j=0;i;i>>=1,++j) if(i&1) x=fa[x][j];
	if(x==y) return x;
	fd(i,17,0) if(fa[x][i]!=fa[y][i]) 
		x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int getdis(int x,int y) {
	int z=lca(x,y);
	return dep[x]+dep[y]-2*dep[z];
}
int d[N],tot;
int ans[N],bz[N];
void solve(int x,int d) {
	if(x==n) {ans[d]++; return;}
	bz[x]=1;
	for(auto [v,dis]:e[x]) {
		if(!bz[v]) solve(v,d+dis);
	}
	bz[x]=0;
}
signed main(){
	read(n,m);
	fo(i,1,m) {
		int u,v; read(u,v);
		g[u].pb(v),g[v].pb(u);
	}
	dfs(1,0);
	fo(i,1,n) for(int v:g[i]) if(fa[i][0]!=v&&fa[v][0]!=i&&v>i) d[++tot]=i,d[++tot]=v;
	d[++tot]=n,d[++tot]=1;
	sort(d+1,d+1+tot,[](int x,int y) {return dfn[x]<dfn[y];});
	tot=unique(d+1,d+1+tot)-d-1;
	int tmp=tot;
	fo(i,1,tmp-1) d[++tot]=lca(d[i],d[i+1]);
	sort(d+1,d+1+tot,[](int x,int y) {return dfn[x]<dfn[y];});
	tot=unique(d+1,d+1+tot)-d-1;
	fo(i,1,tot-1) {
		int u=lca(d[i],d[i+1]),v=d[i+1];
		int dis=getdis(u,v);
		e[u].pb({v,dis}),e[v].pb({u,dis});
	}
	fo(i,1,n) for(int v:g[i]) if(fa[i][0]!=v&&fa[v][0]!=i&&v>i) {
		e[i].pb({v,1}),e[v].pb({i,1});
	}
	solve(1,0);
	fo(i,1,n-1) write(ans[i],' ');
	return 0;
}

Submission Info

Judge Result