用的是魏老师的主席书上二分的做法

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
namespace lzyqwq {
    using u32 = unsigned int; const int N = 1e5 + 5, L = 5e5; 
    const u32 B = 1145141; const int mod = 1e9 + 7;
    int n, m, tmp[100], tcnt, pw[L + 5]; u32 pw2[L + 5]; bool vis[N];
    struct edge { int v, id; edge(int v_ = 0, int id_ = 0) { v = v_; id = id_; } };
    vector<edge> g[N];
    struct node {
        int val; u32 hsh; int len; bool ept;
        node(int val_ = 0, u32 hsh_ = 0, int len_ = 0, bool ept_ = 1) { 
            val = val_; hsh = hsh_; len = len_; ept = ept_;
        }
    };
    node operator+(node u, node v) {
        if (u.ept) return v; if (v.ept) return u;
        return node(1ll * (u.val + 1ll * v.val * pw[u.len]) % mod, 
                    u.hsh + v.hsh * pw2[u.len], u.len + v.len, 0);
    }
    bool operator==(node u, node v) {
        if (!(u.ept & v.ept) && (u.ept | v.ept)) return 0; 
        if (u.ept & v.ept) return 1;
        return u.val == v.val && u.hsh == v.hsh && u.len == v.len;
    }
    struct ChairmanTree {
        node seg[L * 40]; int ls[L * 40], rs[L * 40], rt, cnt;
        void build(int &x, int l, int r) {
            x = ++cnt; seg[x] = node(0, 0, r - l + 1, 0);
            if (l == r) return; int mid = (l + r) >> 1;
            build(ls[x], l, mid); build(rs[x], mid + 1, r); 
        }
        void mdf(int &x, int y, int l, int r, int k, int v) {
            x = ++cnt; if (l == r) return void(seg[x] = node(v, v, 1, 0));
            int mid = (l + r) >> 1;
            if (k <= mid) mdf(ls[x], ls[y], l, mid, k, v), rs[x] = rs[y];
            else mdf(rs[x], rs[y], mid + 1, r, k, v), ls[x] = ls[y];
            seg[x] = seg[ls[x]] + seg[rs[x]];
        }
        node query(int x, int l, int r, int ql, int qr) {
            if (ql > qr) return node();
            if (ql <= l && r <= qr) return seg[x]; 
            int mid = (l + r) >> 1; node ret; 
            if (ql <= mid) ret = query(ls[x], l, mid, ql, qr);
            if (qr > mid) ret = ret + query(rs[x], mid + 1, r, ql, qr); return ret;
        }
        int qry(int x, int y, int l, int r, int ql, int qr) {
            if (seg[x] == seg[y]) return 0; if (l == r) return l;
            int mid = (l + r) >> 1, ret = 0;
            if (qr > mid) ret = qry(rs[x], rs[y], mid + 1, r, ql, qr); 
            if (ret) return ret;
            if (ql <= mid) ret = qry(ls[x], ls[y], l, mid, ql, qr); return ret;
        }
    } T;
    struct dist { 
        int x, l, r; int len() { return r - l + 1; }
        dist(int x_ = 0, int l_ = 0, int r_ = 0) { x = x_; l = l_; r = r_; } 
    } dis[N];
    bool operator<(dist u, dist v) {
        if (u.len() != v.len()) return u.len() < v.len();
        int p = T.qry(u.x, v.x, 1, L, L - u.len() + 1, L); if (!p) return 0; 
        return T.query(u.x, 1, L, p, p).val < T.query(v.x, 1, L, p, p).val;
    }
    struct info {
        int u; dist x; info(int u_ = 0, dist x_ = dist()) { u = u_; x = x_; }
        bool operator<(const info &o) const { return o.x < x; }
    }; priority_queue<info> q;
    template<class T> void read(T &x) {
        x = 0; T f = 1; char c = getchar();
        for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
        for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
    }
    template<class T> void write(T x) {
        if (x > 9) write(x / 10); putchar(x % 10 + 48);
    }
    template<class T> void print(T x, char ed = '\n') {
        if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
    }
    signed Main() {
        read(n); read(m); T.build(T.rt, 1, L);
        for (int i = pw[0] = pw2[0] = 1; i <= L; ++i)
            pw[i] = 1ll * pw[i - 1] * 10 % mod, pw2[i] = pw2[i - 1] * B;
        for (int i = 1, u, v; i <= m; ++i)
            read(u), read(v), g[u].eb(v, i), g[v].eb(u, i);
        dis[1] = dist(T.rt, L, L); q.emplace(1, dis[1]);
        while (q.size()) {
            info t = q.top(); q.pop(); if (vis[t.u]) continue; vis[t.u] = 1;
            for (auto i : g[t.u]) {
                tcnt = 0; int d = i.id, tmpr = t.x.x, cur = 0;
                while (d) tmp[++tcnt] = d % 10, d /= 10; 
                reverse(tmp + 1, tmp + tcnt + 1);
                for (int j = 1; j <= tcnt; ++j) 
                    T.mdf(cur, tmpr, 1, L, t.x.l - j, tmp[j]), tmpr = cur;
                dist res(cur, t.x.l - tcnt, t.x.r);
                if (!dis[i.v].x || res < dis[i.v]) 
                    dis[i.v] = res, q.emplace(i.v, res);
            }
        }
        for (int i = 2; i <= n; ++i)
            print(T.query(dis[i].x, 1, L, dis[i].l, dis[i].r).val);
        return 0;
    }
}
signed main() { return lzyqwq::Main(); }