首先很多人时间复杂度估算错了，这里，我们设 $m=n^2$，这是最坏的情况，所以单次 BFS 的时间复杂度是 $O(n+m)$ 即 $O(n^2)$ 级别的。

每条边都跑一次就是 $O(n^4)$ 了，所以会时超。

我们的做法是把原图最短路的边记录下来，然后删了原图的边再跑最短路，否则直接输出原答案。

因为最短路不大于 $n$，因此时间复杂度是 $O(n^3)$ 级别的，可以通过。

#include<bits/stdc++.h>
#define LL int
using namespace std;
const LL N=405;
struct node
{LL to,num;
};
vector<node>v[N],v2[N];
LL n,m,x,y,pos,dis[N],nxt[N],c[N*N],ans,in[N];
pair<LL,LL>lst[N];
queue<LL>q;
LL work(LL pos)
{for(int i=0;i<=n;i++){dis[i]=1e9;}dis[1]=0;while(!q.empty())q.pop();q.push(1);while(!q.empty()){LL t=q.front();q.pop();for(auto j:v[t]){if(j.num==pos)continue;if(dis[j.to]>dis[t]+1){dis[j.to]=dis[t]+1;if(pos==0)lst[j.to]={t,j.num};q.push(j.to);}if(j.to==n)return dis[n];}}	if(dis[n]==dis[0])return -1;
}
void dg(LL x)
{while(x>1){in[lst[x].second]=1;x=lst[x].first;		}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);v[x].push_back({y,i});}ans=work(0);dg(n);if(dis[n]==dis[0])ans=-1;else ans=dis[n];for(int i=1;i<=m;i++){if(!in[i]){printf("%d\n",ans);continue;}printf("%d\n",work(i));}return 0;
}