OI XXXIII - rzb (Hld)

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

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:256000000")

const int MAXN = 1000005;
const int INF = -1;

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

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

int parent[MAXN];
int depth[MAXN];
int heavy[MAXN];
int head[MAXN];
int pos[MAXN];
int sz[MAXN];
int cur_pos;
int edge_to_node[MAXN];

int tree[4 * MAXN];
bool is_set[4 * MAXN];

struct DSU {
    vector<int> p;
    DSU(int n) {
        p.resize(n + 1);
        iota(p.begin(), p.end(), 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), ry = find(y);
        if (rx != ry) {
            p[rx] = ry;
            return true;
        }
        return false;
    }
};

void dfs_sz(int v, int p, int d) {
    sz[v] = 1;
    parent[v] = p;
    depth[v] = d;
    heavy[v] = -1;

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

        if (u != p) {
            edge_to_node[id] = u;

            dfs_sz(u, v, d + 1);
            sz[v] += sz[u];
            if (sz[u] > max_sz) {
                max_sz = sz[u];
                heavy[v] = u;
            }
        }
    }
}

void dfs_hld(int v, int h) {
    head[v] = h;
    pos[v] = ++cur_pos;

    if (heavy[v] != -1) {
        dfs_hld(heavy[v], h);
    }

    for (auto& edge : adj[v]) {
        int u = edge.first;
        if (u != parent[v] && u != heavy[v]) {
            dfs_hld(u, u);
        }
    }
}

void build_tree(int node, int start, int end) {
    tree[node] = -1;
    is_set[node] = false;
    if (start == end) return;
    int mid = (start + end) / 2;
    build_tree(2 * node, start, mid);
    build_tree(2 * node + 1, mid + 1, end);
}

void update_seg(int node, int start, int end, int l, int r, int val) {
    if (is_set[node]) return;

    if (l <= start && end <= r) {
        if (start == end) {
            tree[node] = val;
            is_set[node] = true;
            return;
        }
    }

    int mid = (start + end) / 2;
    if (l <= mid) update_seg(2 * node, start, mid, l, r, val);
    if (r > mid) update_seg(2 * node + 1, mid + 1, end, l, r, val);

    if (is_set[2 * node] && is_set[2 * node + 1]) {
        is_set[node] = true;
    }
}

void push_all(int node, int start, int end, int val_from_parent) {
    int current_val = (tree[node] != -1) ? tree[node] : val_from_parent;

    if (start == end) {
        tree[node] = current_val;
        return;
    }

    if (tree[node] != -1) current_val = tree[node];

    int mid = (start + end) / 2;
    push_all(2 * node, start, mid, current_val);
    push_all(2 * node + 1, mid + 1, end, current_val);
}

void update_color(int node, int start, int end, int l, int r, int val) {
    if (tree[node] != -1) return;

    if (l <= start && end <= r) {
        tree[node] = val;
        return;
    }

    int mid = (start + end) / 2;
    if (l <= mid) update_color(2 * node, start, mid, l, r, val);
    if (r > mid) update_color(2 * node + 1, mid + 1, end, l, r, val);

    if (tree[2 * node] != -1 && tree[2 * node + 1] != -1) {
        tree[node] = -2;
    }
}

void path_update(int u, int v, int val) {
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        update_color(1, 1, cur_pos, pos[head[u]], pos[u], val);
        u = parent[head[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    if (pos[u] + 1 <= pos[v]) {
        update_color(1, 1, cur_pos, pos[u] + 1, pos[v], val);
    }
}

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

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

    for (int i = 1; i <= m; i++) {
        cin >> all_edges[i].u >> all_edges[i].v;
        all_edges[i].id = i;
        ans[i] = -1;
    }

    DSU dsu(n);
    vector<int> back_edges;
    back_edges.reserve(m);

    for (int i = 1; i <= m; i++) {
        if (dsu.unite(all_edges[i].u, all_edges[i].v)) {
            adj[all_edges[i].u].push_back({all_edges[i].v, i});
            adj[all_edges[i].v].push_back({all_edges[i].u, i});
        } else {
            back_edges.push_back(i);
        }
    }

    cur_pos = 0;
    for (int i = 1; i <= n; i++) {
        if (depth[i] == 0) {
            dfs_sz(i, i, 1);
            dfs_hld(i, i);
        }
    }

    build_tree(1, 1, n);

    for (int id : back_edges) {
        ans[id] = id;

        int u = all_edges[id].u;
        int v = all_edges[id].v;

        path_update(u, v, id);
    }

    push_all(1, 1, n, -1);

    vector<int> final_vals(n + 1);

    function<void(int, int, int)> extract = [&](int node, int start, int end) {
        if (start == end) {
            final_vals[start] = tree[node];
            return;
        }
        int mid = (start + end) / 2;
        extract(2 * node, start, mid);
        extract(2 * node + 1, mid + 1, end);
    };

    extract(1, 1, n);

    for (int i = 1; i <= m; i++) {
        if (ans[i] != -1) continue;

        int node = edge_to_node[i];
        if (node != 0) {
            int p = pos[node];
            int res = final_vals[p];
            if (res != -1) ans[i] = res;
        }
    }

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

    return 0;
}