#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10;
int n,m,dis[N],vis[N],cnt[N];
vector <int> e[N];
priority_queue < pair <int,int> > q;
void dij(){
	memset(dis,0x3f,sizeof(dis));
	dis [1] = 0;
	cnt [1] = 1;
	q.push(make_pair(0,1));
	while(q.size()){
		int x = q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(int i=0;i<e[x].size();i++){
			int y=e[x][i];
			if(dis[y] > dis[x] + 1){
				dis[y] = dis[x] + 1;
				cnt[y] = cnt[x];
				q.push(make_pair(-dis[y],y));
			}
			else if(dis[y] == dis[x]+1){
				cnt[y] = (cnt[y] + cnt[x]) % mod;
			}
		}
	}
	return;
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	cnt[1] = 1;
	dij();
	for(int i=1;i<=n;i++){
		cout << cnt[i] << endl;
	}
	return 0;
}

又是主页里翻的之前的代码