用dfs写的，还要用string来计算路径长度，好烦啊这个题

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
#define MAX 110
#define modmax 100000
struct road {
	int d;//目标城市
	string len;
};
int N, M;
vector< vector<road> >g(MAX);//邻接表
vector<bool>visited;
vector<string>mindist;
string nowdist = "0";//当前从0出发走过的距离
//a小于b返回true;大于或者等于返回false
bool isless(string a, string b) {
	if (a.size() > b.size()) {
		return false;
	}
	else if (a.size() == b.size()) {
		for (int i = 0; i < a.size(); i++) {
			if (a[i] != b[i]) {
				return a[i] < b[i];
			}
		}
		return false;
	}
	else {
		return true;
	}
}
//字符串加法
string stradd(string a, string b) {
	string ls, ss;
	if (a.size() > b.size()) {
		ls = a; ss = b;
	}
	else {
		ls = b; ss = a;
	}
	if (ls.size() == 0)return "0";
	if (ss.size() == 0)ss = "0";
	reverse(ls.begin(), ls.end());
	reverse(ss.begin(), ss.end());

	int carry = 0; int i = 0;
	for (; i < ss.size(); i++) {
		if (ls[i] - '0' + ss[i] - '0' + carry <= 9) {
			ls[i] = (ls[i] - '0' + ss[i] - '0' + carry) + '0';
			carry = 0;
		}
		else {
			ls[i] = (ls[i] - '0' + ss[i] - '0' + carry - 10) + '0';
			carry = 1;
		}
	}
	if (i == ls.size() && carry == 1) {
		ls += "1";
	}
	else {
		while (carry == 1) {
			if (ls[i] - '0' + +carry <= 9) {
				ls[i] = (ls[i] - '0' + carry) + '0';
				carry = 0;
			}
			else {
				ls[i] = (ls[i] - '0' + carry - 10) + '0';
				carry = 1;
				if (i == ls.size() - 1) {
					ls += "1";
					carry = 0;
				}
			}
			i++;
		}
	}

	reverse(ls.begin(), ls.end());
	return ls;
}
//返回2的k次方
string pow(int k) {
	string res = "1";
	while (k != 0) {
		res = stradd(res, res);
		k--;
	}
	return res;
}
//从k城市开始进行遍历
void dfs(int k) {
	visited[k] = true;
	for (int i = 0; i < g[k].size(); i++) {
		int next = g[k][i].d;
		//
		if (next == 0)continue;
		
		if (!visited[next]) {
			if (isless(mindist[next], stradd(nowdist, g[k][i].len))) {
				continue;
			}
			else {
				mindist[next] = stradd(nowdist, g[k][i].len);
			}
			string ori_nowdist = nowdist;
			nowdist = stradd(nowdist, g[k][i].len);
			dfs(next);
			nowdist = ori_nowdist;
		}
	}
	visited[k] = false;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		road r;
		r.len = pow(i); 
		r.d = b; g[a].push_back(r);
		r.d = a; g[b].push_back(r);
	}
	string temp = "1";
	for (int i = 0; i < 200; i++) temp += "0";
	for (int i = 0; i < N; i++) {//初始化
		visited.push_back(false);
		mindist.push_back(temp);
	}
	
	dfs(0);

	
	for (int i = 1; i < mindist.size(); i++) {
		if (mindist[i] == temp) {
			cout << -1 << endl;
		}
		else {
			while (mindist[i].size() > 5) {
				mindist[i].erase(0, mindist[i].size() - 5);
			}
			while (mindist[i][0] == '0') {
				mindist[i].erase(0, 1);
			}
			cout << mindist[i] << endl;
		}
	}
		

	
	return 0;
}