输入数据 1

3 2
0 2
1 2

输出数据 1

-1 -1 2

输入数据 2

5 5
1 2
1 3
3 4
4 5
0 2

输出数据 2

3 3 3 3 2

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,op,kp[300005];
int dis1[300005],dis2[300005];
int head[600005],cnt=1;
bool vis1[300005],vis2[300005];
int ans;
struct node{
    int to,next,val;
}edge[600005];
void add(int x,int y,int z){
    edge[cnt].val=z;
    edge[cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt++;
}
void bfs1(){
    memset(dis1,0x3f,sizeof(dis1));
    queue<int> q;
    dis1[1]=0;
    q.push(1);
    while(q.size()){
        int u=q.front();
        q.pop();
        if(vis1[u]) continue;
        vis1[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(vis1[v]) continue;
            dis1[v]=dis1[u]+1;
            q.push(v);
        }
    }
}
void bfs2(){
    memset(dis2,0x3f,sizeof(dis2));
    queue<int> q;
    dis2[n]=0;
    q.push(n);
    while(q.size()){
        int u=q.front();
        q.pop();
        if(vis2[u]) continue;
        vis2[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(vis2[v]) continue;
            dis2[v]=dis2[u]+1;
            q.push(v);
        }
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        if(x!=0&&y!=0){
            add(x,y,1);
            add(y,x,1);
        }
        else{
            kp[++op]=y;
        }
    }
    bfs1();
    bfs2();
    ans=dis1[n];
    int num1=0x3f3f3f3f3f,num2=0x3f3f3f3f3f;
    for(int i=1;i<=op;i++){
        num1=min(num1,dis1[kp[i]]);
        num2=min(num2,dis2[kp[i]]);
    }
    for(int i=1;i<=n;i++){
        int x=min(ans,min(dis1[i],num1+1)+min(dis2[i],num2+1));
        printf("%lld ",x>=0x3f3f3f3f3f?-1:x);
    }
    return 0;
}