OI XXXIII - rzb (Alt)

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

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;
const int LOGN = 21;

struct Edge {
    int u, v, id;
};

vector<pair<int, int>> adj[MAXN];
int ans[MAXN];
int parent_edge_index[MAXN];

int up[MAXN][LOGN];
int depth[MAXN];
int parent[MAXN];
bool visited[MAXN];

struct DSU_Forest {
    int p[MAXN];
    DSU_Forest(int n) { iota(p, p + n + 1, 0); }
    int find(int x) { return (x == p[x]) ? x : (p[x] = find(p[x])); }
    bool unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            p[rx] = ry;
            return true;
        }
        return false;
    }
};

struct DSU_Path {
    int p[MAXN];
    DSU_Path(int n) { iota(p, p + n + 1, 0); }
    int find(int x) { return (x == p[x]) ? x : (p[x] = find(p[x])); }
    void point_to_parent(int node, int par_node) {
        int root_node = find(node);
        int root_par = find(par_node);
        if (root_node != root_par) {
            p[root_node] = root_par;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<Edge> back_edges;
    back_edges.reserve(m);

    DSU_Forest dsu_forest(n);

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;

        ans[i] = -1;

        if (dsu_forest.unite(u, v)) {
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        } else {
            back_edges.push_back({u, v, i});
        }
    }

    vector<int> q;
    q.reserve(n);

    fill(visited, visited + n + 1, false);

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            depth[i] = 0;
            parent[i] = i;

            for (int k = 0; k < LOGN; ++k)
                up[i][k] = i;

            vector<int> component_q;
            component_q.push_back(i);

            int head = 0;
            while (head < component_q.size()) {
                int u = component_q[head++];

                for (auto& edge : adj[u]) {
                    int v = edge.first;
                    int id = edge.second;

                    if (v != parent[u]) {
                        visited[v] = true;
                        depth[v] = depth[u] + 1;
                        parent[v] = u;
                        parent_edge_index[v] = id;

                        up[v][0] = u;
                        for (int k = 1; k < LOGN; ++k) {
                            up[v][k] = up[up[v][k - 1]][k - 1];
                        }

                        component_q.push_back(v);
                    }
                }
            }
        }
    }

    auto get_lca = [&](int u, int v) -> int {
        if (depth[u] < depth[v]) swap(u, v);
        for (int k = LOGN - 1; k >= 0; --k) {
            if (depth[u] - (1 << k) >= depth[v]) {
                u = up[u][k];
            }
        }
        if (u == v) return u;
        for (int k = LOGN - 1; k >= 0; --k) {
            if (up[u][k] != up[v][k]) {
                u = up[u][k];
                v = up[v][k];
            }
        }
        return up[u][0];
    };

    DSU_Path dsu_path(n);

    for (const auto& edge : back_edges) {
        int u = edge.u;
        int v = edge.v;
        int id = edge.id;

        ans[id] = id;

        int lca = get_lca(u, v);

        auto paint_path = [&](int node, int ancestor) {
            node = dsu_path.find(node);

            while (depth[node] > depth[ancestor]) {
                int edge_idx = parent_edge_index[node];

                if (ans[edge_idx] == -1) {
                    ans[edge_idx] = id;
                }

                dsu_path.point_to_parent(node, parent[node]);

                node = dsu_path.find(node);
            }
        };

        paint_path(u, lca);
        paint_path(v, lca);
    }

    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << (i == m ? "" : " ");
    }
    cout << "\n";

    return 0;
}