#include <bits/stdc++.h>
using namespace std;
#define name "IO"
#define int long long
const int inf = 1e18 + 7;
const int maxn = 3e5 + 5;
int n, e;
vector<pair<int,int>> adj[maxn];
vector<int> ans(maxn, 0);
int cur_val = 1;
int par[maxn], h[maxn], sz[maxn], num[maxn];
int head[maxn], ind[maxn], pos[maxn], arr[maxn];
int cnt, curr;
void dfs(int u, int pre = -1)
{
sz[u] = 1;
for(auto [v, id] : adj[u])
{
if(v == pre) continue;
par[v] = u;
h[v] = h[u] + 1;
num[v] = id;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u, int pre = -1)
{
if(!head[curr])
{
head[curr] = u;
}
ind[u] = curr;
pos[u] = cnt;
arr[cnt] = u;
cnt++;
int nxt = 0;
for(auto [v, id] : adj[u])
{
if(v != pre)
{
if(!nxt || sz[v] > sz[nxt]) nxt = v;
}
}
if(nxt) hld(nxt, u);
for(auto [v, id] : adj[u])
{
if(v != nxt && v != pre)
{
curr++;
hld(v, u);
}
}
}
set<int> st[4 * maxn];
set<int> combine(set<int> x, set<int> y)
{
if(x.size() > y.size())
{
for(auto val : y) x.insert(val);
return x;
}
else
{
for(auto val : x) y.insert(val);
return y;
}
}
void build(int id, int l, int r)
{
if(l == r)
{
st[id].insert(num[arr[l]]);
return;
}
int m = l + r >> 1;
build(id * 2, l, m);
build(id * 2 + 1, m + 1, r);
st[id] = combine(st[id * 2], st[id * 2 + 1]);
}
set<int> get(int id, int l, int r, int u, int v)
{
if(l > v || r < u) return set<int>();
if(l >= u && r <= v) return st[id];
int m = l + r >> 1;
auto x = get(id * 2, l, m, u, v);
auto y = get(id * 2 + 1, m + 1, r, u, v);
auto res = combine(x, y);
return res;
}
void query(int u, int v, int id)
{
set<int> s;
while(ind[u] != ind[v])
{
if(ind[u] > ind[v])
{
s = combine(s, get(1, 1, n, pos[head[ind[u]]], pos[u]));
u = par[head[ind[u]]];
}
else
{
s = combine(s, get(1, 1, n, pos[head[ind[v]]], pos[v]));
v = par[head[ind[v]]];
}
}
if(h[u] < h[v]) s = combine(s, get(1, 1, n, pos[u] + 1, pos[v]));
else s = combine(s, get(1, 1, n, pos[v] + 1, pos[u]));
for(auto x : s)
{
if(!ans[x])
{
ans[x] = cur_val;
cur_val++;
}
}
ans[id] = cur_val;
cur_val++;
}
void solve()
{
cin >> n >> e;
vector<pair<int,int>> edge(e + 1);
for(int i = 1; i <= e; i++)
{
int u, v;
cin >> u >> v;
edge[i] = {u, v};
}
vector<int> in(e + 1, 0);
for(int i = 1; i < n; i++)
{
int id;
cin >> id;
in[id] = 1;
auto [u, v] = edge[id];
adj[u].push_back({v, id});
adj[v].push_back({u, id});
}
curr = cnt = 1;
dfs(1);
hld(1);
build(1, 1, n);
for(int i = 1; i <= e; i++)
{
if(in[i])
{
if(!ans[i])
{
ans[i] = cur_val;
cur_val++;
}
}
else
{
auto [u, v] = edge[i];
query(u, v, i);
}
}
for(int i = 1; i <= e; i++) cout << ans[i] << " ";
}
signed main()
{
if (fopen (name".INP", "r"))
{
freopen (name".INP", "r", stdin);
freopen (name".OUT", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
clock_t start = clock();
int t = 1;
while(t--) solve();
std::cerr << "Time: " << clock() - start << "ms\n";
return 0;
}
