#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define file(name) \
if(fopen(name".inp", "r")) \
freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
const int MAX = 3e5 + 5;
const int LOG = 18;
int N, M, ans[MAX], depth[MAX], numChild[MAX], local[MAX], par[MAX], header[MAX];
vector <int> adj[MAX], mst;
vector <pair <int, int>> edges;
void dfs(int u, int p) {
numChild[u] = 1;
par[u] = p;
int Max = 0, id = 0;
for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != p) {
int v = adj[u][i];
dfs(v, u);
numChild[u] += numChild[v];
if(Max < numChild[v]) {
Max = numChild[v];
id = i;
}
}
swap(adj[u][id], adj[u][0]);
}
void HLD(int u) {
static int run = 0;
local[u] = ++run;
for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != par[u]) {
int v = adj[u][i];
if(i == 0 && 2 * numChild[v] >= numChild[u]) {
depth[v] = depth[u];
header[v] = header[u];
} else {
depth[v] = depth[u] + 1;
header[v] = v;
}
HLD(v);
}
}
int itMin[4 * MAX], ind[MAX], pos[MAX];
void build(int idx, int l, int r) {
itMin[idx] = -1;
if(l == r) {
pos[l] = idx;
} else {
int mid = l + r >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
}
}
void updateMin(int u, int val) {
u = pos[u];
itMin[u] = val;
while(u > 1) {
u >>= 1;
itMin[u] = min(itMin[u << 1], itMin[u << 1 | 1]);
}
}
int getMin(int idx, int l, int r, int u, int v) {
if(l > v || r < u) return INT_MAX;
if(l >= u && r <= v) return itMin[idx];
int mid = l + r >> 1;
return min(getMin(idx << 1, l, mid, u, v), getMin(idx << 1 | 1, mid + 1, r, u, v));
}
int find_pos_min(int idx, int l, int r, int u, int v) {
if(l > v || r < u || itMin[idx] > -1) return -1;
if(l == r) return l;
int mid = l + r >> 1;
int x = find_pos_min(idx << 1, l, mid, u, v);
if(x != -1) return x;
return find_pos_min(idx << 1 | 1, mid + 1, r, u, v);
}
void get_path(int l, int r, vector <int> &res) {
while(getMin(1, 1, N, l, r) == -1) {
int x = find_pos_min(1, 1, N, l, r);
res.push_back(ind[x]);
updateMin(x, 0);
}
}
vector <int> get_path(int u, int v) {
vector <int> ans;
if(depth[u] < depth[v]) swap(u, v);
while(depth[u] > depth[v]) {
get_path(local[header[u]], local[u], ans);
u = par[header[u]];
}
while(header[u] != header[v]) {
get_path(local[header[u]], local[u], ans);
get_path(local[header[v]], local[v], ans);
u = par[header[u]], v = par[header[v]];
}
if(local[u] > local[v]) swap(u, v);
get_path(local[u] + 1, local[v], ans);
return ans;
}
void you_make_it(void) {
cin >> N >> M;
edges.resize(M + 1);
for (int i = 1; i <= M; ++i) {
cin >> edges[i].fi >> edges[i].se;
}
for (int i = 1; i < N; ++i) {
int x; cin >> x;
auto [u, v] = edges[x];
adj[u].push_back(v);
adj[v].push_back(u);
mst.push_back(x);
}
fill(ans + 1, ans + M + 1, -1);
dfs(1, 0);
depth[1] = header[1] = 1;
HLD(1);
for (int x : mst) {
auto &[u, v] = edges[x];
if(v == par[u]) swap(u, v);
ind[local[v]] = x;
}
build(1, 1, N);
int cur = 1;
for (int i = 1; i <= M; ++i) {
if(ans[i] != -1) continue;
auto [u, v] = edges[i];
vector <int> res = get_path(u, v);
sort(res.begin(), res.end());
for (auto x : res) {
ans[x] = cur++;
}
if(ans[i] == -1) {
ans[i] = cur++;
}
}
for (int i = 1; i <= M; ++i) cout << ans[i] << " \n"[i == M];
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
file("riggedroads");
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
