#include  "bits/stdc++.h"
using namespace std;
int main()
{
	int n,m,i,a,b,mi,j;
	cin>>n>>m;
	vector<int>x[n+1];
	for (i=0;i<m;i++)
	{
		cin>>a>>b;
		if (a==b)
		{
			continue;
		}
		x[a].push_back(b);
		x[b].push_back(a);
	}
	mi=1;
	int y[n+1];
	for (i=1;i<=n;i++)
	{
		y[i]=1<<30;
	}
	y[1]=1;
	int z[n+1];
	memset(z,0,sizeof(z));
	z[1]=1;
	for (i=1;i<=n;i++)
	{
		for (j=0;j<x[i].size();j++)
		{
			if (y[x[i][j]]==y[i]+1)
			{
				z[x[i][j]]+=z[i];
			}
			else
			{
				if (y[x[i][j]]>y[i]+1)
				{
					z[x[i][j]]=z[i];
				}
			}
			y[x[i][j]]=min(y[x[i][j]],y[i]+1); 
		}
	}
	for (i=1;i<=n;i++)
	{
		cout<<z[i]%100003<<"\n";
	}
}