#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int const maxn=1e6+10;
int const mod=10003;
int n,m,u,v;
int dis[maxn],ans[maxn];
vector<int>g[maxn];
bitset<maxn>vis;
priority_queue<pii,vector<pii>,greater<pii> >q;
void dij()
{
    dis[1]=0;
    ans[1]=1;
    q.push({0,1});
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(auto i:g[u])
        {
            if(dis[i]>dis[u]+1)
            {
                dis[i]=dis[u]+1;
                q.push({dis[i],i});
            }
            else if(dis[i]==dis[u]+1)
                ans[i]=(ans[i]+ans[u])%mod;
        }
    }
}
signed main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    fill(dis+1,dis+n+1,INT_MAX);
    dij();
    for(int i=1;i<=n;i++)
        printf("%d\n",dis[i]);
    return 0;
}