我一开始不会这道题，然后就随便写，写完之后就随机修改直到过了大样例为止。

然后得了88分

做法显然错。就是先求出1,2的单源最短路，然后看看除1,2外每个点看看能不能连，能连就连。最后再看1,2有没有能连的，能连就连上。其中：枚举两个点的复杂度高达 $\Theta(n^2)$，并且松弛的过程也不是很有道理。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0;
	char e=getchar();
	while(e<'0'||e>'9') {
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x;
}
const int N=400005,M=2000005;
int head[N],ver[M],nxt[M],idx=-1;
void add(int x,int y) {
	++idx;
	ver[idx]=y;
	nxt[idx]=head[x];
	head[x]=idx;
}
int dis[2][N],vis[N];
void dijkstra(int s,int op) {
	memset(dis[op],0x3f,sizeof dis[op]);
	dis[op][s]=0;
	memset(vis,0,sizeof vis);
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	q.push({0,s});
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u]; ~i; i=nxt[i]) {
			int v=ver[i];
			if(dis[op][v]>dis[op][u]+1) {
				dis[op][v]=dis[op][u]+1;
				q.push({dis[op][v],v});
			}
		}
	}
}
int n,m,ans;
int hax(int x,int y) {
	return x*10000000+y;
}
unordered_map<int,bool>mp;
signed main() {
//	freopen("ex.in","r",stdin);
//	freopen("out.txt","w",stdout);
	memset(head,-1,sizeof head);
	R(n),R(m);
	for(int i=1; i<=m; ++i) {
		int R(u),R(v);
		add(u,v),add(v,u);
		mp[hax(u,v)]=mp[hax(v,u)]=1;
	}
	dijkstra(1,0);
	dijkstra(2,1);
	for(int i=3; i<=n; ++i) {
		for(int j=3; j<i; ++j) {
			if(mp[hax(i,j)])continue;
			if(dis[0][i]+dis[1][j]>=4&&dis[1][i]+dis[0][j]>=4) {
				++ans;
				dis[0][i]=min(dis[0][i],dis[0][j]+1);
				dis[0][j]=min(dis[0][j],dis[0][i]+1);
				dis[1][i]=min(dis[1][i],dis[1][j]+1);
				dis[1][j]=min(dis[1][j],dis[1][i]+1);
//				cout<<i<<" "<<j<<"\n";
			}
		}
	}
	for(int i=1;i<=n;++i){
		if(dis[0][i]>=4&&dis[1][i]>=4&&!mp[hax(1,i)]){
			++ans;
		}
		
	}
	cout<<ans<<"\n";
	return 0;
}