听灌佬多

#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
const int N = 2e6 + 10;
#define endl '\n'
#define int long long
int dis[N];
int ans[N] = {0, 1};
vector<int>g[N];
int n, m;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	memset(dis, 0x7f, sizeof(dis));
	queue<int>q;
	q.push(1);
	dis[1] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i : g[u]) {
			if (dis[u] + 1 < dis[i] || ans[i] == 0) {
				ans[i] = ans[u];
				dis[i] = dis[u] + 1;
				q.push(i);
			} else if (dis[i] == dis[u] + 1) {
				ans[i] += ans[u];
				ans[i] %= 100003;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}