N 个城市，标号从 0 到 N?1，M 条道路，第 K 条道路（K 从 0 开始）的长度为 2^k，求编号为 0 的城市到其他城市的最短距离。
输入格式
第一行两个正整数 N,M，表示有 N 个城市，M 条道路。
接下来 M 行两个整数，表示相连的两个城市的编号。
输出格式
N?1 行，表示 0 号城市到其他城市的最短路，如果无法到达，输出 ?1，数值太大的以 mod100000 的结果输出。
数据范围
2≤N≤100,
1≤M≤500
输入样例：
4 4
1 2
2 3
1 3
0 1
输出样例：
8
9
11
思路：显然，权值为正，所以考虑用dijkstra（这里为了方便我用了堆优化版的）。
注意点
1.如果第k行的两个点已经在之前经过其他点连通了，那么第k行的权值必然不是最小的，直接可以忽略不计算，所以我们需要用并查集来判断是否连通。
2.无向图
3.数据范围大，取模用快速幂
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue>
# include<map>
# include<string>
# include<cstring>
#include<limits.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII;
const int mod=100000;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const ll inf=0x3f3f3f3f;ll n,m,head[MAX],tot,a[MAX],f[MAX];
bool vis[MAX];struct edge{
int to,dis,next;
}e[MAX];struct Node{
ll pos;ll dis;bool operator<(const Node &x)const{
return dis>x.dis ;}
};ll find(ll x){
if(x != f[x]) f[x] = find(f[x]);return f[x];
}ll qp(ll a,ll b){
//快速幂模板ll res = 1;while(b){
if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;
}void add(ll x,ll y ,ll z){
e[++tot].to = y;e[tot].dis = z;e[tot].next = head[x];head[x] = tot;
}void dijkstra(){
//dijkstra模板memset(a,inf ,sizeof a);std::priority_queue<Node>q;q.push({
1,0});a[1] = 0;while(q.size()){
Node now = q.top() ;q.pop() ;ll x = now.pos ;if(vis[x]) continue;vis[x] = true;for(ll i = head[x] ; i ;i = e[i].next ){
ll y = e[i].to ;if( a[y] > a[x] + e[i].dis ){
a[y] = a[x] + e[i].dis;q.push({
y,a[y]}); }}}
}
int main(){
std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) f[i] = i;for(int i=0;i<m;i++){
ll u,v;cin>>u>>v;u++;v++;int fa = find(u), fb = find(v);//cout<<fa<<" "<<fb<<endl;if(fa!=fb){
//判断是否之前已经可以到达，不可以就保存f[fa] = fb;ll c = qp(2,i); add(u,v,c);add(v,u,c);}}dijkstra(); for(int i=2;i<=n;i++) if(a[i] > inf/2 ) cout<<"-1\n";else cout<<a[i]%mod<<"\n"; return 0;
}