#include <bits/stdc++.h> 
using namespace std;
const int maxn=1e6+1;
const int maxm=2e6+1;
long long cnt[maxn<<1];
int head[maxm];int n,m;
const int Inf=9999999;
struct Edge{
	int u,v,w,next;
}e[maxm*2];
int len=0;
void ins(int u,int v,int w){
	e[++len].u=u;
	e[len].v=v;
	e[len].w=w;
	e[len].next=head[u];
	head[u]=len;
};
struct Node{
	int num,dis;
	Node(int x,int y){
		num=x;
		dis=y;
	}
};
bool operator<(const Node &a,const Node &b){
		return a.dis>b.dis;
}
int d[maxm];
int a[11451][11451];
void dj(int u){
	priority_queue <Node> q;
	q.push(Node(u,0));
	cnt[1]=1;
	memset(d,Inf,sizeof(d));
	d[u]=0;
	while(!q.empty()){
		int u=q.top().num;
		q.pop();
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].v;
			if(d[v]>=d[u]+e[i].w){
				d[v]=d[u]+e[i].w;
				cnt[v]++;
				q.push(Node(v,d[v]));
			}
		}
	}
}
void read(){
	scanf("%d %d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		ins(u,v,1);
		ins(v,u,1);
	}
}
int main(){
	read();
	dj(1);
	for(int i=0;i<=maxn;i++){
		if(cnt[i]==0)	continue;
		if(cnt[i]==0&&d[i]<Inf)	cout<<"0";
		cout<<cnt[i]%1000003<<endl;
	}
	return 0;
}