题解

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;char k;bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
struct B{
	int x,y;
	B(int _x=0,int _y=0):x(_x),y(_y){}
	bool operator <(const B &t)const{return x+y==t.x+t.y?y<t.y:x+y<t.x+t.y;}
	bool operator ==(const B &t)const{return x==t.x&&y==t.y;}
};
map<int,int>U[100015],S[100015];
struct E{int u,t;}G[400005];
int f[100005],s,m,tot,dis[100005][2],q[200005];
bool r[200005];vector<B>tem;
void add(int u,int v){
	G[++tot].u=v;G[tot].t=f[u];f[u]=tot;
	G[++tot].u=u;G[tot].t=f[v];f[v]=tot;
}
int main(){q[0]=1;r[0]=0;
	for(int T=read;T--;){
		s=read,m=read;tot=0;
		memset(f,0,s+1<<2);
		memset(dis,-1,s+1<<3);
		for(int i=1;i<=m;++i) add(read,read);
		for(int i=0;i<=s+5;++i)S[i].clear(),U[i].clear();
		dis[1][0]=0;
		for(int i=0,j=1;i!=j;++i){
			int n=q[i];
			for(int x=f[n];x;x=G[x].t)
				if(!~dis[G[x].u][!r[i]]){
					r[j]=!r[i];q[j]=G[x].u;++j;
					dis[G[x].u][!r[i]]=dis[n][r[i]]+1;
				}
		}int ans=0;
		if(!~dis[1][1])ans=s-1;
		else if(dis[1][1]==1)ans=s;
			else{tem.clear();
				for(int i=2;i<=s;++i){
					int x=dis[i][0],y=dis[i][1];
					if(y>x)swap(x,y);
					++S[x][y];tem.push_back(B(x,y));
				}S[dis[1][1]][0]=1;
				sort(tem.begin(),tem.end());
				B v(114514,-1);
				for(int i=0;i<tem.size();++i){
					if(v==tem[i]) continue;
					v=tem[i];
					int cnt=S[v.x][v.y],h=S[v.x-1][v.y-1],p=U[v.x+1][v.y-1];
					if(!h)ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=cnt:cnt+1>>1);
					else if(!p)ans+=cnt;
					else ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=min(cnt,p):min(cnt,p)+1>>1);
				}
			}
		printf("%d\n",ans);
	}
	return 0;
}