#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
priority_queue<pair<int,int> > q;
int vis[1000005],head[10000005],tot,d[1000005],ans[1000005],mod=100003;
struct jd{
	int v,nxt;
}a[2000005];
void add(int u,int v){
	a[++tot].v=v;
	a[tot].nxt=head[u];
	head[u]=tot;
}
void dji(){
	vis[1]=1;ans[1]=1;
	q.push(make_pair(0,1));
	memset(d,0x3f,sizeof d);d[1]=0;
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=a[i].nxt){
			int y=a[i].v;
			if(d[y]>d[x]+1){
				d[y]=d[x]+1;
				q.push(make_pair(-d[y],y));
			}
			else if(d[y]==d[x]+1){
				ans[y]+=ans[x];
				ans[y]%=mod;
				cout<<y<<" "<<ans[y]<<endl;
			}
		}
	}
	return;
}
signed main(){
	int n;
	cin>>n;
	int m;
	cin>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dji();
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}