#include <iostream> #include <vector> #include <algorithm> #include <string> #include <queue> #include <set> #include <map> #define rep(i, s, e) for (ll i = s; i < e; i++) #define upmax(a, b) a = max(a, b) #define upmin(a, b) a = min(a, b) using namespace std; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>; const ll INF = 1e18; /* vll depth, par, ans; map<pll, ll> edges_idx; vvll tree; void dfs(ll node, ll papa) { for (auto& nei : tree[node]) { if (nei == papa) continue; depth[nei] = depth[node] + 1; par[nei] = node; dfs(nei, node); } } void path(ll a, ll b, vll& idx) { if (depth[b] > depth[a]) swap(a, b); while (depth[a] > depth[b]) { ll mn = min(a, par[a]); ll mx = max(a, par[a]); a = par[a]; ll i = edges_idx[{mn, mx}]; if (ans[i] == -1) { idx.push_back(i); } } while (a != b) { ll mn = min(a, par[a]); ll mx = max(a, par[a]); a = par[a]; ll i = edges_idx[{mn, mx}]; if (ans[i] == -1) { idx.push_back(i); } mn = min(b, par[b]); mx = max(b, par[b]); b = par[b]; i = edges_idx[{mn, mx}]; if (ans[i] == -1) { idx.push_back(i); } } } void solve() { ll n, m; cin >> n >> m; vpll edges(m); vector<bool> R(m); rep(i, 0, m) { cin >> edges[i].first >> edges[i].second; edges[i].first--, edges[i].second--; edges[i] = { min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second) }; edges_idx[edges[i]] = i; } tree.clear(), tree.resize(n); depth.clear(), depth.resize(n, 0); par.clear(), par.resize(n, -1); rep(i, 0, n - 1) { ll e; cin >> e; e--; R[e] = 1; tree[edges[e].first].push_back(edges[e].second); tree[edges[e].second].push_back(edges[e].first); } ans.clear(), ans.resize(m, -1); dfs(0, -1); ll curW = 1; rep(i, 0, m) { if (ans[i] != -1) continue; else if (R[i]) { ans[i] = curW; curW++; } else { vll idx; path(edges[i].first, edges[i].second, idx); sort(idx.begin(), idx.end()); rep(j, 0, idx.size()) { ans[idx[j]] = curW; curW++; } ans[i] = curW; curW++; } } rep(i, 0, m) cout << ans[i] << ' '; cout << endl; } */ vll papa, god, depth, par, sz; vvll tree; map<pll, ll> idx; void dfs(ll node, ll p) { for (auto& nei : tree[node]) { if (nei == p) continue; par[nei] = node; depth[nei] = depth[node] + 1; dfs(nei, node); } } void init(ll n) { papa.clear(), papa.resize(n); god.clear(), god.resize(n); sz.clear(), sz.resize(n, 1); rep(i, 0, n) papa[i] = i, god[i] = i; } ll find(ll node) { if (papa[node] == node) return node; papa[node] = find(papa[node]); return papa[node]; } bool unite(ll a, ll b) { a = find(a), b = find(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; papa[b] = a; if (depth[god[b]] < depth[god[a]]) { god[a] = god[b]; } return true; } vll calc(ll a, ll b) { vll res; while (a != b) { a = find(a), b = find(b); if (a == b) break; if (depth[god[a]] < depth[god[b]]) swap(a, b); // Connect the lower one with it's direct father a = god[a]; unite(a, par[a]); res.push_back(idx[{a, par[a]}]); } return res; } void solve() { ll n, m; cin >> n >> m; vpll edges(m); rep(i, 0, m) { cin >> edges[i].first >> edges[i].second; edges[i].first--, edges[i].second--; idx[edges[i]] = i; idx[{edges[i].second, edges[i].first}] = i; } vll R(n - 1); vector<bool> ST(m); tree.clear(), tree.resize(n); par.clear(), par.resize(n, -1); depth.clear(), depth.resize(n, 0); rep(i, 0, n - 1) { cin >> R[i]; R[i]--; ST[R[i]] = true; tree[edges[R[i]].first].push_back(edges[R[i]].second); tree[edges[R[i]].second].push_back(edges[R[i]].first); } dfs(0, -1); init(n); ll val = 1; vll ans(m, -1); rep(i, 0, m) { if (ans[i] != -1) { continue; } else if (ST[i]) { ll a = edges[i].first, b = edges[i].second; a = find(a), b = find(b); if (depth[god[a]] < depth[god[b]]) swap(a, b); // Connect the lower one with it's direct father a = god[a]; unite(a, par[a]); ans[i] = val; val++; } else { vll edges_update = calc(edges[i].first, edges[i].second); sort(edges_update.begin(), edges_update.end()); rep(j, 0, edges_update.size()) { ans[edges_update[j]] = val; //cout << edges_update[j] << ' '; val++; } //cout << '\n'; ans[i] = val; val++; } } rep(i, 0, m) cout << ans[i] << ' '; cout << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); }