自闭了

#include<bits/stdc++.h>
using namespace std;

struct node{
	int no,val;
};

bool operator<(const node &A,const node &B){
	return A.val>B.val;
}

int n,m,x,y,len[1000050],dist[1000050],ans[1000050];
vector<int>T[1000050];
priority_queue<node>q;

int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		T[x].push_back(y);
		T[y].push_back(x);
		len[x]++;
		len[y]++;
	}node X,k;
	X.no=1;X.val=0;
	q.push(X);
	dist[1]=0;ans[1]=1;
	for(int i=2;i<=n;i++)dist[i]=99999999;
	while(!q.empty()){
		X=q.top();
		q.pop();
		for(int i=0;i<len[X.no];i++){
			if(dist[X.no]+1<dist[T[X.no][i]]){
				dist[T[X.no][i]]=dist[X.no]+1;
				k.no=T[X.no][i];k.val=dist[X.no]+1;
				ans[T[X.no][i]]=ans[X.no];
				ans[T[X.no][i]]%=100001;
				q.push(k);
			}else if(dist[X.no]+1==dist[T[X.no][i]]){
				ans[T[X.no][i]]+=ans[X.no];
				ans[T[X.no][i]]%=100001;
			}
		}
	}/*X.no=1;X.val=0;
	q.push(X);
	while(!q.empty()){
		X=q.top();
		q.pop();
		for(int i=0;i<len[X.no];i++){
			if(dist[X.no]+1==dist[T[X.no][i]]){
				k.no=T[X.no][i];k.val=dist[X.no]+1;
				ans[T[X.no][i]]++;
				ans[T[X.no][i]]%=100003;
				q.push(k);
			}
				
		}
	}*/cout<<1<<endl;
	for(int i=2;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}