RT

#include<bits/stdc++.h>
using namespace std;
struct edge{
	long long to,l;
};
typedef pair<long long,long long> PII;
vector<edge> v[2000009];
bool vis[2000009];
long long sum[2000009];
long long dis[2000009];
long long n,m,s,e,x,y;
priority_queue<PII,vector<PII>,greater<PII> > pq;
void dijkstra(long long x){
	sum[1]=1;
	for(int i=0;i<2000009;i++)dis[i]=2147483647;
	dis[x]=0;
	pq.push({0,x});
	while(!pq.empty()){
		PII t=pq.top();
		pq.pop(); 
		long long id=t.second;
		long long d=t.first;
		if(vis[id]==true)continue;
		vis[id]=true;
		for(long long i=0;i<v[id].size();i++){
			edge y=v[id][i];
			long long to=y.to;
			if(dis[to]>d+1){
				dis[to]=d+len;
				sum[to]=sum[d];
				pq.push({dis[to],to});
			}
			else if(dis[to]==d+len){
				sum[to]+=sum[d];
				sum[to]%=100003;
			}
		}
	}
} 
int main(){
	cin>>n>>m;
	for(long long i=1;i<=m;i++){
		cin>>x>>y;
		v[x].push_back({y,1});
		v[y].push_back({x,1});
	}
	dijkstra(1);
	for(int i=1;i<=n;i++){
		cout<<sum[i]<<endl;
	}
	return 0;
}