#include<iostream>
#include<algorithm>//包含fill函数
using namespace std;

#define INF 0x3f3f3f
const int maxn = 1005;
int n,m;
int G[maxn][maxn];
int fa[maxn];
int dis[maxn];
bool vis[maxn];

int f(int x)
{
	int s = 1;
	for (int i = 1; i <= x; i++)
	{
		s = (s*2)%100000;//距离
	}
	return s;
}

void dijkstra(int x)
{
	fill(vis,vis+maxn,false);//按照单元赋值,将一个区间的元素都赋予val值
	                         //函数参数:fill(vec.begin(),vec.end(),val);val为将要替换的值
	fill(dis,dis+maxn,INF);
	for(int i = 0; i < n; i++)  dis[i] = G[x][i];
	dis[x] = 0;
	vis[x] = true;
	for (int i = 1; i < n; i++)
	{
		int min = INF;
		int u = -1;
		for (int j = 0; j < n; j++)
		{
			if (vis[j] == false && dis[j] < min)
			{
				min = dis[j];
				u = j;
			}
		}
		if (u == -1) return;
		vis[u] = true;
		for (int j = 0; j < n; j++)
		{
			if (vis[j] == false && dis[j] > dis[u] + G[u][j])
				dis[j] = dis[u] + G[u][j];
		}
	}
}

int find(int x)
{
	while (x!=fa[x])  x = fa[x];
	return x;
}

int main()
{
	while (cin>>n>>m)
	{
		if (n == 0) break;
		int a,b;
		for (int i = 0; i < n; i++)  fa[i] = i;
		fill (G[0],G[0] + maxn*maxn,INF);//初始化
		for (int i = 0; i < m; i++)
		{
			cin>>a>>b;
			int fx = find(a);
			int fy = find(b);
			if (fx != fy)
			{
				fa[fx] = fy;
				G[a][b] = G[b][a] = f(i);
			}
			else continue;
		}
		dijkstra(0);
		for (int i = 1; i < m; i++)
		{
			if(dis[i] == INF) cout<<"-1"<<endl;
			else  cout<<dis[i]%100000<<endl;
		}
	}
	return 0;
}