#include <bits/stdc++.h>
using namespace std;
struct Tree {
vector<int> depth, parent, siz, head, begin, end;
Tree(int n, const vector<vector<int>> &adj) : depth(n), parent(n), siz(n), head(n), begin(n), end(n) {
auto scout = [&](auto self, int u, int p) -> void {
depth[u] = p == -1 ? 0 : depth[p] + 1;
parent[u] = p;
siz[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
self(self, v, u);
siz[u] += siz[v];
}
};
scout(scout, 0, -1);
int tim = 0;
auto decompose = [&](auto self, int u, int h) -> void {
head[u] = h;
begin[u] = tim++;
int heavy = -1;
for (int v : adj[u]) {
if (v == parent[u]) continue;
if (heavy == -1 || siz[v] > siz[heavy]) heavy = v;
}
if (heavy != -1) {
self(self, heavy, h);
}
for (int v : adj[u]) {
if (v == parent[u] || v == heavy) continue;
self(self, v, v);
}
end[u] = tim;
};
decompose(decompose, 0, 0);
}
int getDepth(int u) {
return depth[u];
}
int getNode(int u) {
return begin[u];
}
vector<array<int, 2>> getPath(int u, int v, bool includeLCA = true) {
vector<array<int, 2>> res;
while (head[u] != head[v]) {
if (depth[head[u]] > depth[head[v]]) swap(u, v);
res.push_back({ begin[head[v]], begin[v] + 1 });
v = parent[head[v]];
}
if (depth[u] > depth[v]) swap(u, v);
int l = begin[u] + (!includeLCA);
int r = begin[v] + 1;
if (l < r) res.push_back({l, r});
return res;
}
};
struct Paint {
int n;
vector<int> color;
Paint(int n) : n(n), color(4 * n, -1) {}
void paint(int ql, int qr, int c) {
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) {
color[idx] = c;
return;
}
if (color[idx] != -1) {
color[2 * idx + 1] = color[2 * idx + 2] = color[idx];
color[idx] = -1;
}
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
};
dfs(dfs, 0, 0, n);
}
int getColor(int i) {
int idx = 0, l = 0, r = n;
while (l + 1 < r) {
if (color[idx] != -1) return color[idx];
int m = (l + r) >> 1;
if (i < m) {
idx = 2 * idx + 1;
r = m;
} else {
idx = 2 * idx + 2;
l = m;
}
}
return color[idx];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<int, 2>> edges(m);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
edges[i] = {u, v};
}
vector<bool> is_tree_edge(m, false);
for (int i = 0; i < n - 1; i++) {
int p;
cin >> p;
p--;
is_tree_edge[p] = true;
}
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
if (!is_tree_edge[i]) continue;
auto [u, v] = edges[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
Tree tree(n, adj);
Paint paint(n);
for (int i = m - 1; i >= 0; i--) {
if (is_tree_edge[i]) continue;
auto [u, v] = edges[i];
for (auto [l, r] : tree.getPath(u, v, false)) {
paint.paint(l, r, i);
}
}
vector<vector<int>> inbox(m);
for (int i = 0; i < m; i++) {
if (!is_tree_edge[i]) continue;
auto [u, v] = edges[i];
if (tree.getDepth(u) > tree.getDepth(v)) swap(u, v);
int color = paint.getColor(tree.getNode(v));
if (color != -1) inbox[color].push_back(i);
}
int val = 1;
vector<int> w(m);
for (int i = 0; i < m; i++) {
if (!is_tree_edge[i]) {
sort(inbox[i].begin(), inbox[i].end());
for (int j : inbox[i]) {
w[j] = val++;
}
w[i] = val++;
} else {
auto [u, v] = edges[i];
if (tree.getDepth(u) > tree.getDepth(v)) swap(u, v);
int color = paint.getColor(tree.getNode(v));
if (color == -1) {
w[i] = val++;
}
}
}
for (int i = 0; i < m; i++) {
cout << w[i] << " \n"[i == m - 1];
}
}
