Submission #1267313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267313		tubication	Rigged Roads (NOI19_riggedroads)	C++20	Compilation error	0 ms	0 KiB

riggedroads

/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⡀⡀⡀⠠⢄⣠⣴⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⣿⣾⣆⡀⡀⢻
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⡀⡀⠄⡐⣰⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⣿⣿⣿⣿⣿⣷⡀⠈
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠉⡀⢀⣔⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⡄
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⢀⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣦⣿⠰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⡠⣷⣿⡟⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣰⣿⣿⣿⠇⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠈⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣴⣿⣿⣿⣿⡀⢸⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⠁⣼⣿⣿⣿⣿⣿⡀⠐⣿⣿⠁⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⣿⡀⡆⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡀⣺⣿⣿⣿⣿⣿⣿⡀⡀⢀⢈⡀⠈⢙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⡀⠹⡿⣸⡇⢺⣿⣿⣿⢻⣿
⣿⣿⣿⣿⣿⣿⠁⢰⣿⡅⠻⣿⣿⣿⣿⡀⣿⡀⣿⡀⠐⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⠂⡀⣶⢁⣿⣯⢸⣿⣿⠇⢸⣿
⣿⣿⣿⣿⣿⠁⡀⡀⢿⣿⡀⠉⢻⣿⣿⡇⣿⣷⡀⡀⣅⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣼⡆⠋⣾⣿⣿⢸⣿⡿⡀⣾⣿
⣿⣿⣿⣿⠃⢠⣮⡀⡀⣈⠃⠘⣦⣴⣦⣤⣾⣿⣿⣶⣿⡈⣿⡀⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⣾⣿⣁⣾⣿⣿⡟⠸⠋⡤⢀⣿⣿
⣿⣿⣿⠃⢀⣾⣿⡧⠨⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⡈⡆⠈⣿⣿⣿⣿⣿⡿⠁⣴⣿⣿⣿⣿⣿⣿⣿⣷⠿⢿⡗⢸⣿⠏
⣿⣿⠏⡀⣽⣿⣿⡇⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣄⢸⣄⠻⡿⠟⢁⣴⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⣀⠅⣿⡟⣠
⣿⠏⡀⢲⣿⣿⣿⠇⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣷⣴⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⡿⠘⣁⣾⣿
⠟⡀⢔⣿⣿⣿⣿⠂⣿⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣶⠠⣿⣿⣿
⡀⡀⣺⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⠇⣼⣿⣿⣿
⡀⡐⣿⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⢠⣿⣿⡀⣿⣿⣿⣿
⡀⢿⣿⣿⣿⣿⣿⡂⢿⣿⣷⡀⡀⡀⡀⡀⡀⡀⡀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⢀⣿⣿⡏⢰⣿⣿⣿⣿
⢀⣿⣿⣿⣿⣿⣿⡅⢸⣿⣿⣿⣷⣦⣤⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⣀⣀⣤⣶⣿⣿⣿⡀⢼⣿⠫⣿⣿
⢨⣿⣿⣿⣿⣿⣿⡧⠐⣿⣿⣿⣿⣿⣿⣿⠉⡉⠉⣉⣉⠉⣉⣉⢉⠉⢉⡉⠉⠉⠉⠉⠉⠉⢹⣿⣿⣿⣿⣿⡏⡀⣺⡟⢰⣿⣿
⣸⣿⣿⣿⣿⣿⣿⣿⡀⣻⣿⣿⣿⣿⣿⣿⡆⣿⢸⣿⣿⡀⣿⣿⡟⡀⣿⣿⠁⣿⣿⡀⣿⠃⣼⣿⣿⣿⣿⡿⡀⡀⡿⠁⣾⣿⣿
⢺⡟⣿⣿⣿⣿⣿⣿⡀⡀⠻⣿⣿⣿⣿⣿⣿⡈⢸⣿⣿⡀⣿⣿⣷⢸⣿⣿⡀⣿⣿⠰⠋⣴⣿⣿⣿⡿⠋⡀⡀⡀⠁⢠⣿⣿⣿
⠸⡇⠹⣿⣿⣿⣿⣿⣇⡀⡀⡀⠛⢿⣿⣿⣿⣿⣄⠙⡿⢰⣿⣿⣿⢸⣿⣿⠠⡿⠋⣤⣿⣿⣿⠟⠉⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿
⡀⠈⡀⠙⢿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⣈⠉⠛⠿⢿⣶⣤⣉⣙⢉⣉⣉⣁⣤⠾⠛⠋⠉⡀⡀⡀⡀⡀⢀⣠⣤⣴⠴⠷⠶⠚⠋
⡀⡀⢰⣷⣄⡀⠛⠿⣿⣷⡀⣆⡀⡀⡀⠘⣿⣿⣿⣶⠖⣀⠲⣶⣶⣶⣶⠆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⢈⠉⠉⠉⠉
⡀⡀⡪⣿⣿⣧⡀⢠⣤⣀⡁⡀⡀⡀⡀⣆⠈⠿⠛⣠⣿⣿⣦⠈⢿⣿⡟⢠⡀⡀⡀⡀⡀⡀⡀⡀⢽⣿⠿⡿⣿⣿⢿⡿⣿⣿⣿
⣀⡀⠱⣿⣿⣿⡀⣿⣿⣿⠟⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣴⣿⠇⡀⡀⡀⣄⡀⡠⡆⠘⣿⢸⣗⣥⣿⣿⣿⣰⣴⣬
⠋⢠⣦⡀⡹⠻⣷⡟⠛⠁⡀⡀⡀⡀⡀⡀⡀⠉⠉⠋⠙⠛⠛⠛⠛⠛⠉⠉⡀⡀⡀⡀⢹⣦⠘⢿⡀⣿⡎⣾⣿⣫⡶⣾⡿⣽⣭ 
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))

#define ll long long
#define ld long double
#define ull unsigned long long

#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll pair <ll, ll>

#define vvi vector <vector <int>>

#define all(v) (v).begin(), (v).end()
#define __builtin_popcount __builtin_popcountll

#define fi first
#define se second

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }   

const int nmax = 3e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r) {
    return uniform_int_distribution <long long>(l, r)(rng);
}

/** END OF TEMPLATE **/

int n, m, u, v, r[nmax];
pii edges[nmax];

vector <pii> adj[nmax];

int a[nmax], cnt = 1;

int h[nmax], id[nmax];
int up[nmax][20];

void dfs(int u, int p) {
    up[u][0] = (p == -1 ? u : p);

    for (auto [v, w]: adj[u]) {
        if (v == p) continue;
        h[v] = h[u] + 1;
        id[v] = w;

        up[v][0] = u;

        for (int j = 1; j < 20; ++j)
            up[v][j] = up[up[v][j - 1]][j - 1];
        
        dfs(v, u);
    }
}

int query_lca(int u, int v) {
    if (h[u] != h[v]) {
        if (h[u] < h[v]) swap(u, v);

        int k = h[u] - h[v];
        for (int j = 0; (1 << j) <= k; ++j)
            if (k >> j & 1) u = up[u][j];
    }

    if (u == v) return u;

    int k = __lg(h[u]);
    for (int j = k; j >= 0; --j) {
        if (up[u][j] != up[v][j]) {
            u = up[u][j], v = up[v][j];
        }
    }

    return up[u][0];
}

int par[nmax];

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;

    if (h[x] > h[y]) swap(x, y);
    par[y] = x;
}

bool check(int x, int y) {
    return find(x) == find(y);
}

set <int> tmp;
void get(int u, int anc) {
    while (!check(u, anc)) {
        int v = find(u);
        tmp.insert(id[v]);
        unite(v, up[v][0]);
    }
}

int main() {
    synchronize;

    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> edges[i].fi >> edges[i].se;

    for (int i = 1; i < n; i++) {
        cin >> r[i];

        int idx = r[i];
        auto [u, v] = edges[idx];

        adj[u].emplace_back(v, idx);
        adj[v].emplace_back(u, idx);
    }

    h[1] = id[1] = 0;
    dfs(1, -1);
    for (int i = 1; i <= n; i++) par[i] = i;
    fill(a + 1, a + m + 1, -1);

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

        auto [u, v] = edges[i];

        if (check(u, v)) {
            a[i] = cnt++;
            continue;
        }
        
        tmp.clear();
        int x = query_lca(u, v);
        get(u, x); get(v, x);
        
        tmp.erase(i);

        for (int y: tmp) a[y] = cnt++;
        a[i] = cnt++;
    }

    for (int i = 1; i <= m; i++) cout << a[i] << ' ';

    return (0 ^ 0);
}/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⡀⡀⡀⠠⢄⣠⣴⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⣿⣾⣆⡀⡀⢻
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⡀⡀⠄⡐⣰⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⣿⣿⣿⣿⣿⣷⡀⠈
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠉⡀⢀⣔⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⡄
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⢀⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣦⣿⠰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⡠⣷⣿⡟⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣰⣿⣿⣿⠇⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠈⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣴⣿⣿⣿⣿⡀⢸⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⠁⣼⣿⣿⣿⣿⣿⡀⠐⣿⣿⠁⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⣿⡀⡆⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡀⣺⣿⣿⣿⣿⣿⣿⡀⡀⢀⢈⡀⠈⢙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⡀⠹⡿⣸⡇⢺⣿⣿⣿⢻⣿
⣿⣿⣿⣿⣿⣿⠁⢰⣿⡅⠻⣿⣿⣿⣿⡀⣿⡀⣿⡀⠐⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⠂⡀⣶⢁⣿⣯⢸⣿⣿⠇⢸⣿
⣿⣿⣿⣿⣿⠁⡀⡀⢿⣿⡀⠉⢻⣿⣿⡇⣿⣷⡀⡀⣅⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣼⡆⠋⣾⣿⣿⢸⣿⡿⡀⣾⣿
⣿⣿⣿⣿⠃⢠⣮⡀⡀⣈⠃⠘⣦⣴⣦⣤⣾⣿⣿⣶⣿⡈⣿⡀⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⣾⣿⣁⣾⣿⣿⡟⠸⠋⡤⢀⣿⣿
⣿⣿⣿⠃⢀⣾⣿⡧⠨⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⡈⡆⠈⣿⣿⣿⣿⣿⡿⠁⣴⣿⣿⣿⣿⣿⣿⣿⣷⠿⢿⡗⢸⣿⠏
⣿⣿⠏⡀⣽⣿⣿⡇⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣄⢸⣄⠻⡿⠟⢁⣴⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⣀⠅⣿⡟⣠
⣿⠏⡀⢲⣿⣿⣿⠇⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣷⣴⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⡿⠘⣁⣾⣿
⠟⡀⢔⣿⣿⣿⣿⠂⣿⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣶⠠⣿⣿⣿
⡀⡀⣺⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⠇⣼⣿⣿⣿
⡀⡐⣿⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⢠⣿⣿⡀⣿⣿⣿⣿
⡀⢿⣿⣿⣿⣿⣿⡂⢿⣿⣷⡀⡀⡀⡀⡀⡀⡀⡀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⢀⣿⣿⡏⢰⣿⣿⣿⣿
⢀⣿⣿⣿⣿⣿⣿⡅⢸⣿⣿⣿⣷⣦⣤⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⣀⣀⣤⣶⣿⣿⣿⡀⢼⣿⠫⣿⣿
⢨⣿⣿⣿⣿⣿⣿⡧⠐⣿⣿⣿⣿⣿⣿⣿⠉⡉⠉⣉⣉⠉⣉⣉⢉⠉⢉⡉⠉⠉⠉⠉⠉⠉⢹⣿⣿⣿⣿⣿⡏⡀⣺⡟⢰⣿⣿
⣸⣿⣿⣿⣿⣿⣿⣿⡀⣻⣿⣿⣿⣿⣿⣿⡆⣿⢸⣿⣿⡀⣿⣿⡟⡀⣿⣿⠁⣿⣿⡀⣿⠃⣼⣿⣿⣿⣿⡿⡀⡀⡿⠁⣾⣿⣿
⢺⡟⣿⣿⣿⣿⣿⣿⡀⡀⠻⣿⣿⣿⣿⣿⣿⡈⢸⣿⣿⡀⣿⣿⣷⢸⣿⣿⡀⣿⣿⠰⠋⣴⣿⣿⣿⡿⠋⡀⡀⡀⠁⢠⣿⣿⣿
⠸⡇⠹⣿⣿⣿⣿⣿⣇⡀⡀⡀⠛⢿⣿⣿⣿⣿⣄⠙⡿⢰⣿⣿⣿⢸⣿⣿⠠⡿⠋⣤⣿⣿⣿⠟⠉⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿
⡀⠈⡀⠙⢿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⣈⠉⠛⠿⢿⣶⣤⣉⣙⢉⣉⣉⣁⣤⠾⠛⠋⠉⡀⡀⡀⡀⡀⢀⣠⣤⣴⠴⠷⠶⠚⠋
⡀⡀⢰⣷⣄⡀⠛⠿⣿⣷⡀⣆⡀⡀⡀⠘⣿⣿⣿⣶⠖⣀⠲⣶⣶⣶⣶⠆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⢈⠉⠉⠉⠉
⡀⡀⡪⣿⣿⣧⡀⢠⣤⣀⡁⡀⡀⡀⡀⣆⠈⠿⠛⣠⣿⣿⣦⠈⢿⣿⡟⢠⡀⡀⡀⡀⡀⡀⡀⡀⢽⣿⠿⡿⣿⣿⢿⡿⣿⣿⣿
⣀⡀⠱⣿⣿⣿⡀⣿⣿⣿⠟⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣴⣿⠇⡀⡀⡀⣄⡀⡠⡆⠘⣿⢸⣗⣥⣿⣿⣿⣰⣴⣬
⠋⢠⣦⡀⡹⠻⣷⡟⠛⠁⡀⡀⡀⡀⡀⡀⡀⠉⠉⠋⠙⠛⠛⠛⠛⠛⠉⠉⡀⡀⡀⡀⢹⣦⠘⢿⡀⣿⡎⣾⣿⣫⡶⣾⡿⣽⣭ 
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))

#define ll long long
#define ld long double
#define ull unsigned long long

#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll pair <ll, ll>

#define vvi vector <vector <int>>

#define all(v) (v).begin(), (v).end()
#define __builtin_popcount __builtin_popcountll

#define fi first
#define se second

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }   

const int nmax = 3e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r) {
    return uniform_int_distribution <long long>(l, r)(rng);
}

/** END OF TEMPLATE **/

int n, m, u, v, r[nmax];
pii edges[nmax];

vector <pii> adj[nmax];

int a[nmax], cnt = 1;

int h[nmax], id[nmax];
int up[nmax][20];

void dfs(int u, int p) {
    up[u][0] = (p == -1 ? u : p);

    for (auto [v, w]: adj[u]) {
        if (v == p) continue;
        h[v] = h[u] + 1;
        id[v] = w;

        up[v][0] = u;

        for (int j = 1; j < 20; ++j)
            up[v][j] = up[up[v][j - 1]][j - 1];
        
        dfs(v, u);
    }
}

int query_lca(int u, int v) {
    if (h[u] != h[v]) {
        if (h[u] < h[v]) swap(u, v);

        int k = h[u] - h[v];
        for (int j = 0; (1 << j) <= k; ++j)
            if (k >> j & 1) u = up[u][j];
    }

    if (u == v) return u;

    int k = __lg(h[u]);
    for (int j = k; j >= 0; --j) {
        if (up[u][j] != up[v][j]) {
            u = up[u][j], v = up[v][j];
        }
    }

    return up[u][0];
}

int par[nmax];

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;

    if (h[x] > h[y]) swap(x, y);
    par[y] = x;
}

bool check(int x, int y) {
    return find(x) == find(y);
}

set <int> tmp;
void get(int u, int anc) {
    while (!check(u, anc)) {
        int v = find(u);
        tmp.insert(id[v]);
        unite(v, up[v][0]);
    }
}

int main() {
    synchronize;

    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> edges[i].fi >> edges[i].se;

    for (int i = 1; i < n; i++) {
        cin >> r[i];

        int idx = r[i];
        auto [u, v] = edges[idx];

        adj[u].emplace_back(v, idx);
        adj[v].emplace_back(u, idx);
    }

    h[1] = id[1] = 0;
    dfs(1, -1);
    for (int i = 1; i <= n; i++) par[i] = i;
    fill(a + 1, a + m + 1, -1);

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

        auto [u, v] = edges[i];

        if (check(u, v)) {
            a[i] = cnt++;
            continue;
        }
        
        tmp.clear();
        int x = query_lca(u, v);
        get(u, x); get(v, x);
        
        tmp.erase(i);

        for (int y: tmp) a[y] = cnt++;
        a[i] = cnt++;
    }

    for (int i = 1; i <= m; i++) cout << a[i] << ' ';

    return (0 ^ 0);
}

Compilation message (stderr)

riggedroads.cpp:277:10: error: redefinition of 'template<class X, class Y> bool maximize(X&, const Y&)'
  277 |     bool maximize(X &x, const Y &y) {
      |          ^~~~~~~~
riggedroads.cpp:65:10: note: 'template<class X, class Y> bool maximize(X&, const Y&)' previously declared here
   65 |     bool maximize(X &x, const Y &y) {
      |          ^~~~~~~~
riggedroads.cpp:286:10: error: redefinition of 'template<class X, class Y> bool minimize(X&, Y)'
  286 |     bool minimize(X &x, Y y) {
      |          ^~~~~~~~
riggedroads.cpp:74:10: note: 'template<class X, class Y> bool minimize(X&, Y)' previously declared here
   74 |     bool minimize(X &x, Y y) {
      |          ^~~~~~~~
riggedroads.cpp:294:11: error: redefinition of 'const int nmax'
  294 | const int nmax = 3e5 + 5;
      |           ^~~~
riggedroads.cpp:82:11: note: 'const int nmax' previously defined here
   82 | const int nmax = 3e5 + 5;
      |           ^~~~
riggedroads.cpp:295:10: error: redefinition of 'const long long int mod'
  295 | const ll mod = 1e9 + 7;
      |          ^~~
riggedroads.cpp:83:10: note: 'const long long int mod' previously defined here
   83 | const ll mod = 1e9 + 7;
      |          ^~~
riggedroads.cpp:296:10: error: redefinition of 'const long long int inf'
  296 | const ll inf = 1e18;
      |          ^~~
riggedroads.cpp:84:10: note: 'const long long int inf' previously defined here
   84 | const ll inf = 1e18;
      |          ^~~
riggedroads.cpp:298:12: error: redefinition of 'std::mt19937_64 rng'
  298 | mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
      |            ^~~
riggedroads.cpp:86:12: note: 'std::mt19937_64 rng' previously declared here
   86 | mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
      |            ^~~
riggedroads.cpp:299:4: error: redefinition of 'long long int rngesus(long long int, long long int)'
  299 | ll rngesus(ll l, ll r) {
      |    ^~~~~~~
riggedroads.cpp:87:4: note: 'long long int rngesus(long long int, long long int)' previously defined here
   87 | ll rngesus(ll l, ll r) {
      |    ^~~~~~~
riggedroads.cpp:305:5: error: redefinition of 'int n'
  305 | int n, m, u, v, r[nmax];
      |     ^
riggedroads.cpp:93:5: note: 'int n' previously declared here
   93 | int n, m, u, v, r[nmax];
      |     ^
riggedroads.cpp:305:8: error: redefinition of 'int m'
  305 | int n, m, u, v, r[nmax];
      |        ^
riggedroads.cpp:93:8: note: 'int m' previously declared here
   93 | int n, m, u, v, r[nmax];
      |        ^
riggedroads.cpp:305:11: error: redefinition of 'int u'
  305 | int n, m, u, v, r[nmax];
      |           ^
riggedroads.cpp:93:11: note: 'int u' previously declared here
   93 | int n, m, u, v, r[nmax];
      |           ^
riggedroads.cpp:305:14: error: redefinition of 'int v'
  305 | int n, m, u, v, r[nmax];
      |              ^
riggedroads.cpp:93:14: note: 'int v' previously declared here
   93 | int n, m, u, v, r[nmax];
      |              ^
riggedroads.cpp:305:17: error: redefinition of 'int r [300005]'
  305 | int n, m, u, v, r[nmax];
      |                 ^
riggedroads.cpp:93:17: note: 'int r [300005]' previously declared here
   93 | int n, m, u, v, r[nmax];
      |                 ^
riggedroads.cpp:306:5: error: redefinition of 'std::pair<int, int> edges [300005]'
  306 | pii edges[nmax];
      |     ^~~~~
riggedroads.cpp:94:5: note: 'std::pair<int, int> edges [300005]' previously defined here
   94 | pii edges[nmax];
      |     ^~~~~
riggedroads.cpp:308:14: error: redefinition of 'std::vector<std::pair<int, int> > adj [300005]'
  308 | vector <pii> adj[nmax];
      |              ^~~
riggedroads.cpp:96:14: note: 'std::vector<std::pair<int, int> > adj [300005]' previously declared here
   96 | vector <pii> adj[nmax];
      |              ^~~
riggedroads.cpp:310:5: error: redefinition of 'int a [300005]'
  310 | int a[nmax], cnt = 1;
      |     ^
riggedroads.cpp:98:5: note: 'int a [300005]' previously declared here
   98 | int a[nmax], cnt = 1;
      |     ^
riggedroads.cpp:310:14: error: redefinition of 'int cnt'
  310 | int a[nmax], cnt = 1;
      |              ^~~
riggedroads.cpp:98:14: note: 'int cnt' previously defined here
   98 | int a[nmax], cnt = 1;
      |              ^~~
riggedroads.cpp:312:5: error: redefinition of 'int h [300005]'
  312 | int h[nmax], id[nmax];
      |     ^
riggedroads.cpp:100:5: note: 'int h [300005]' previously declared here
  100 | int h[nmax], id[nmax];
      |     ^
riggedroads.cpp:312:14: error: redefinition of 'int id [300005]'
  312 | int h[nmax], id[nmax];
      |              ^~
riggedroads.cpp:100:14: note: 'int id [300005]' previously declared here
  100 | int h[nmax], id[nmax];
      |              ^~
riggedroads.cpp:313:5: error: redefinition of 'int up [300005][20]'
  313 | int up[nmax][20];
      |     ^~
riggedroads.cpp:101:5: note: 'int up [300005][20]' previously declared here
  101 | int up[nmax][20];
      |     ^~
riggedroads.cpp:315:6: error: redefinition of 'void dfs(int, int)'
  315 | void dfs(int u, int p) {
      |      ^~~
riggedroads.cpp:103:6: note: 'void dfs(int, int)' previously defined here
  103 | void dfs(int u, int p) {
      |      ^~~
riggedroads.cpp:332:5: error: redefinition of 'int query_lca(int, int)'
  332 | int query_lca(int u, int v) {
      |     ^~~~~~~~~
riggedroads.cpp:120:5: note: 'int query_lca(int, int)' previously defined here
  120 | int query_lca(int u, int v) {
      |     ^~~~~~~~~
riggedroads.cpp:353:5: error: redefinition of 'int par [300005]'
  353 | int par[nmax];
      |     ^~~
riggedroads.cpp:141:5: note: 'int par [300005]' previously declared here
  141 | int par[nmax];
      |     ^~~
riggedroads.cpp:355:5: error: redefinition of 'int find(int)'
  355 | int find(int x) {
      |     ^~~~
riggedroads.cpp:143:5: note: 'int find(int)' previously defined here
  143 | int find(int x) {
      |     ^~~~
riggedroads.cpp:360:6: error: redefinition of 'void unite(int, int)'
  360 | void unite(int x, int y) {
      |      ^~~~~
riggedroads.cpp:148:6: note: 'void unite(int, int)' previously defined here
  148 | void unite(int x, int y) {
      |      ^~~~~
riggedroads.cpp:368:6: error: redefinition of 'bool check(int, int)'
  368 | bool check(int x, int y) {
      |      ^~~~~
riggedroads.cpp:156:6: note: 'bool check(int, int)' previously defined here
  156 | bool check(int x, int y) {
      |      ^~~~~
riggedroads.cpp:372:11: error: redefinition of 'std::set<int> tmp'
  372 | set <int> tmp;
      |           ^~~
riggedroads.cpp:160:11: note: 'std::set<int> tmp' previously declared here
  160 | set <int> tmp;
      |           ^~~
riggedroads.cpp:373:6: error: redefinition of 'void get(int, int)'
  373 | void get(int u, int anc) {
      |      ^~~
riggedroads.cpp:161:6: note: 'void get(int, int)' previously defined here
  161 | void get(int u, int anc) {
      |      ^~~
riggedroads.cpp:381:5: error: redefinition of 'int main()'
  381 | int main() {
      |     ^~~~
riggedroads.cpp:169:5: note: 'int main()' previously defined here
  169 | int main() {
      |     ^~~~