#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int read ()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return f*x;
}
const int N=1e6+5,M=2e6+5,mod=1e5+3;
int n,m,dis[N],ans[N],had[N],to[M*2],nxt[M*2],p,a1,b1;
void add(int x,int y)
{
nxt[++p]=had[x];
to[p]=y;
had[x]=p;
}
void bfs()
{
queue <int> que;
que.push(1);
while(que.size())
{
int u=que.front(); que.pop();
for(int i=had[u];i;i=nxt[i])
{
int v=to[i];
if(!dis[v])
{
dis[v]=dis[u]+1;
que.push(v);
}
if(dis[v]==dis[u]+1) ans[v]=(ans[v]+ans[u])%mod;
}
}
}
int main()
{
n=read(); m=read();
for(int i=1;i<=m;i++)
{
a1=read(); b1=read();
add(a1,b1); add(b1,a1);
}
ans[1]=1; bfs(); ans[1]=1;
for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
return 0;
}
