#include <bits/stdc++.h> using namespace std; #define name "TENBAI" #define fi first #define se second #define int long long #define endl '\n' #define setmin(x, y) x = min((x), (y)) #define setmax(x, y) x = max((x), (y)) #define sqr(x) ((x) * (x)) #define all(x) x.begin(), x.end() mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count()); int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);} const int NM = 3e5 + 5; const int LG = 20; int n, m, ans[NM], cr, up[NM][LG], par[NM], dep[NM], jump[NM]; pair<int, int> e[NM]; map<pair<int, int>, int> mp; vector<int> g[NM], siu; void dfs(int u) { for (int v : g[u]) { g[v].erase(find(all(g[v]), u)); par[v] = up[v][0] = u; dep[v] = dep[u] + 1; dfs(v); } } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); if (dep[u] > dep[v]) { int t = dep[u] - dep[v]; for (int i = 0; (1 << i) <= t; i++) if (t >> i & 1) u = up[u][i]; } if (u == v) return u; for (int i = LG - 1; i >= 0; i--) if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i]; return up[u][0]; } void add(int u, int l) { while (dep[u] > dep[l]) { if (jump[u] == u) { siu.push_back(mp[{u, par[u]}]); jump[u] = jump[l]; u = par[u]; } else { int t = jump[u]; u = t; jump[u] = jump[l]; } } } void solve() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> e[i].fi >> e[i].se; mp[{e[i].fi, e[i].se}] = mp[{e[i].se, e[i].fi}] = i; } for (int i = 1; i <= n; i++) jump[i] = i; for (int i = 1; i < n; i++) { int x; cin >> x; g[e[x].fi].push_back(e[x].se); g[e[x].se].push_back(e[x].fi); } dfs(1); for (int i = 1; i <= n; i++) for (int j = 1; j < LG; j++) up[i][j] = up[up[i][j - 1]][j - 1]; for (int i = 1; i <= m; i++) { // cout << i << ' ' << cr << endl; int u = e[i].fi, v = e[i].se; if (v == par[u] || u == par[v]) { if (!ans[i]) { ans[i] = ++cr; int x = (dep[u] > dep[v] ? u : v); jump[x] = jump[par[x]]; } } else { int l = lca(u, v); add(u, l); add(v, l); sort(all(siu)); for (int t : siu) ans[t] = ++cr; ans[i] = ++cr; siu.clear(); } } for (int i = 1; i <= m; i++) cout << ans[i] << ' '; } signed main() { if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); } else if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tc = 1; // cin >> tc; while (tc--) solve(); }

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~