OI XXXIII - rzb

// https://szkopul.edu.pl/problemset/problem/nNRmLjU-KBuT9rVjbu8Hl8js/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001, sizik2 = 21;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

using P = std::pair<int, int>;

std::vector<P> kra[sizik];
P kraw[sizik];

int pre[sizik], post[sizik], curr;
int parent[sizik], parent_edge_idx[sizik];
int up[sizik][sizik2];
int depth[sizik];
void DFS(int v, int p, int d, int p_edge) {
    depth[v] = d;
    parent[v] = p;
    parent_edge_idx[v] = p_edge;
    up[v][0] = p;
    for (int i = 1; i < sizik2; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    pre[v] = ++curr;
    for (const auto& [u, idx] : kra[v]) {
        if (u == p) continue;
        DFS(u, v, d + 1, idx);
    }
    post[v] = ++curr;
}

inline bool is_ancestor(int v, int u) {
    return pre[v] <= pre[u] && post[u] <= post[v];
}

inline int lca(int a, int b) {
    if (is_ancestor(a, b)) return a;
    if (is_ancestor(b, a)) return b;
    for (int i = sizik2 - 1; i >= 0; i--) {
        if (!is_ancestor(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

struct DSU {
    std::vector<int> rep;
    int n;
    DSU(int nn) : n(nn) {
        rep.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            rep[i] = i;
        }
    }
    int Find(int a) { return rep[a] == a ? a : rep[a] = Find(rep[a]); }
    void Union(int a, int b) {
        a = Find(a), b = Find(b);
        if (depth[a] > depth[b]) {
            rep[a] = rep[b];
        } else {
            rep[b] = rep[a];
        }
    }
};

int ans[sizik];

void solve() {
    int n, m;
    std::cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        std::cin >> a >> b;

        kraw[i] = {a, b};
    }

    if (m == 1) {
        std::cout << "-1\n";
        return;
    }

    DSU MstDSU(n);

    std::vector<int> kraw_nd;
    kraw_nd.reserve(std::max(m - n, 1));

    for (int i = 1; i <= m; i++) {
        const auto& [a, b] = kraw[i];
        if (MstDSU.Find(a) == MstDSU.Find(b)) {
            kraw_nd.push_back(i);
        } else {
            MstDSU.Union(a, b);
            kra[a].push_back({b, i});
            kra[b].push_back({a, i});
        }
    }

    DSU dsu(n);

    DFS(1, 1, 1, -1);

    auto paint = [&dsu](int a, int L, int val) -> void {
        a = dsu.Find(a), L = dsu.Find(L);
        if (a == L) return;
        while (depth[a] > depth[L]) {
            ans[parent_edge_idx[a]] = val;
            int p = dsu.Find(parent[a]);
            dsu.Union(a, p);
            a = p;
        }
    };

    for (const auto& idx : kraw_nd) {
        ans[idx] = idx;
        const auto& [a, b] = kraw[idx];
        int L = lca(a, b);

        paint(a, L, idx);
        paint(b, L, idx);
    }

    for (int i = 1; i <= m; i++) {
        if (ans[i] == 0) ans[i] = -1;
        std::cout << ans[i] << ' ';
    }
    std::cout << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}