bfs应该也可以吧……

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5,mod = 100003;
queue <int> f,t;
vector <int> q[N];
int n,ggb,a,b,ans[N],m[N];
map <int,bool> d[N];
int main()
{
	cin >> n >> ggb;
	for(int i = 1;i <= ggb;i ++)
	{
		cin >> a >> b;
		if(a == b || d[a][b]) continue;
		d[a][b] = d[b][a] = 1;
		q[a].push_back(b);
		q[b].push_back(a);
	}
	m[0] = 0;
	ans[1] = 1;
	f.push(1);
	t.push(0);
//	cout << endl;
	while(!f.empty())
	{
		int v = f.front();
		int ti = t.front();
//		cout << v << ' ' << ti << endl;
		t.pop();
		f.pop();
		ti ++;
		for(int i = 0;i < q[v].size();i ++)
		{
			int u = q[v][i];
			if(!m[u] && u != 1 || m[u] > ti)
			{
				m[u] = ti;
				f.push(u);
				t.push(ti);
			}
			if(m[u] == ti) ans[u] ++,ans[u] %= mod;
		}
	}
	for(int i = 1;i <= n;i ++) printf("%d\n",ans[i]);
	return 0;
}