#include <bits/stdc++.h>
using namespace std;
#define task "palace"
#define etr "\n"
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pli pair<long long,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define bg begin
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define lwb lower_bound
#define upb upper_bound
#define range(x, l, r) x+l, x+1+r
#define all(x) (x).bg(), (x).end()
#define compact(x) x.resize(unique(all(x)) - (x).bg())
#define sq(x) ((x)*(x))
auto start = chrono::high_resolution_clock::now();
void start_timer()
{
start = chrono::high_resolution_clock::now();
}
ld elapsed()
{
auto current = chrono::high_resolution_clock::now();
ld duration = chrono::duration_cast<chrono::nanoseconds>(current - start).count();
return duration / 1e9;
}
void freop()
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
template<class U, class V> istream& operator >> (istream& in, pair<U, V>& p)
{
in >> p.fi >> p.se;
return in;
}
template<class U, class V> ostream& operator << (ostream& out, pair<U, V> p)
{
out << "{" << p.fi << ' ' << p.se << "}";
return out;
}
template<class T> ostream& operator << (ostream& out, vector<T>& v)
{
out << "{";
for (int i=0; i<v.size(); i++)
{
out << v[i];
if (i != v.size() - 1) out << ", ";
}
out << "}";
return out;
}
const int N=3e5, M=1e5, mod=1e9+7;
int n, m;
pii edge[N+5];
int r[N+5];
namespace Sub1
{
struct DSU
{
int connections = 0;
vector<int> par;
DSU(int sz) : par(n+5, -1) {}
int root(int node)
{
return par[node] < 0 ? node : par[node] = root(par[node]);
}
bool connect(int u, int v)
{
u = root(u), v = root(v);
if (u == v) return false;
if (-par[u] < -par[v]) swap(u, v);
connections++;
par[u] += par[v];
par[v] = u;
return true;
}
bool same(int u, int v)
{
return root(u) == root(v);
}
};
void solve()
{
int w[m+5];
for (int i=1; i<=m; i++) w[i] = i;
int tmp[m+5];
bool mark[m+5] = {false};
for (int i=1; i<n; i++) mark[r[i]] = true;
do
{
DSU dsu(n);
bool ok = true;
for (int i=1; i<=m; i++) tmp[w[i]] = i;
for (int i=1; i<=m; i++)
{
if (!dsu.connect(edge[tmp[i]].fi, edge[tmp[i]].se)) continue;
if (!mark[tmp[i]])
{
ok = false;
break;
}
}
if (ok)
{
for (int i=1; i<=m; i++) cout << w[i] << ' ';
return;
}
} while (next_permutation(range(w, 1, m)));
}
}
namespace Sub7
{
vector<pii> adj[N+5];
int sub[N+5];
int timer = 0, a[N+5], in[N+5], out[N+5], head[N+5], p[N+5];
bool mark[N+5], used[N+5];
struct SegmentTree
{
bool lazy[N*4+5];
SegmentTree()
{
memset(lazy, 0, sizeof(lazy));
}
void update(int id, int l, int r, int pos)
{
if (pos<l || pos>r) return;
if (l == r)
{
lazy[id] = true;
return;
}
int mid = (l+r) >> 1;
update(id*2, l, mid, pos);
update(id*2+1, mid+1, r, pos);
lazy[id] = lazy[id*2] && lazy[id*2+1];
}
int walk(int id, int l, int r, int u, int v)
{
if (v<l || u>r || lazy[id]) return 0;
if (l == r) return l;
int mid = (l+r) >> 1;
int res;
if (res = walk(id*2+1, mid+1, r, u, v)) return res;
return walk(id*2, l, mid, u, v);
}
} seg;
int edgeID[N+5], edgeToNode[N+5];
int init(int par, int u)
{
sub[u] = 1;
for (pii p : adj[u])
{
int v = p.fi;
if (v == par) continue;
edgeID[v] = p.se;
edgeToNode[p.se] = v;
sub[u] += init(u, v);
}
return sub[u];
}
void dfs(int par, int u, int hd)
{
head[u] = hd;
in[u] = ++timer;
p[u] = par;
a[in[u]] = u;
int child = 0;
for (pii p : adj[u])
{
int v = p.fi;
if (v == par) continue;
if (sub[v] > sub[child]) child = v;
}
if (child) dfs(u, child, hd);
for (pii p : adj[u])
{
int v = p.fi;
if (v == par || v == child) continue;
dfs(u, v, v);
}
out[u] = timer;
}
bool edgeUsed[N+5];
vector<int> order;
int hld(int u, int v)
{
//cout << u << ' ' << v << ": ";
int dist = 0;
vector<int> path;
while (head[u] != head[v])
{
if (in[u] < in[v]) swap(u, v);
while (true)
{
int node = seg.walk(1, 1, n, in[head[u]], in[u]);
if (node == 0) break;
//cout << a[node] << ": " << edgeID[a[node]] << "!" << etr;
dist++;
seg.update(1, 1, n, node);
path.pb(edgeID[a[node]]);
}
u = p[head[u]];
}
if (u == v)
{
//cout << dist << etr;
sort(all(path));
for (int i : path)
{
edgeUsed[i] = true;
order.pb(i);
}
return dist;
}
if (in[u] > in[v]) swap(u, v);
while (true)
{
int node = seg.walk(1, 1, n, in[u]+1, in[v]);
if (node == 0) break;
//cout << a[node] << ": " << edgeID[a[node]] << "!" << etr;
dist++;
seg.update(1, 1, n, node);
path.pb(edgeID[a[node]]);
}
sort(all(path));
for (int i : path)
{
edgeUsed[i] = true;
order.pb(i);
}
//cout << dist << etr;
return dist;
}
int ans[N+5];
void solve()
{
for (int i=1; i<n; i++)
{
int u = edge[r[i]].fi, v = edge[r[i]].se;
adj[u].pb({v, r[i]});
adj[v].pb({u, r[i]});
mark[r[i]] = true;
}
init(0, 1);
dfs(0, 1, 1);
int cur = 1;
for (int i=1; i<=m; i++)
{
if (edgeUsed[i]) continue;
if (mark[i])
{
ans[i] = cur;
used[ans[i]] = true;
cur = ans[i] + 1;
seg.update(1, 1, n, in[edgeToNode[i]]);
//cout << i << ": " << ans[i] << etr;
continue;
}
ans[i] = cur + hld(edge[i].fi, edge[i].se);
//cout << i << ": " << ans[i] << etr;
used[ans[i]] = true;
cur = ans[i] + 1;
}
//cout << order << etr;
int j = 1;
for (int i : order)
{
while (used[j]) j++;
ans[i] = j;
used[j] = true;
}
for (int i=1; i<=m; i++) cout << ans[i] << ' ';
}
};
void process()
{
cin >> n >> m;
for (int i=1; i<=m; i++)
{
cin >> edge[i];
}
for (int i=1; i<n; i++) cin >> r[i];
sort(range(r, 1, n-1));
Sub7::solve();
//if (m <= 9) Sub1::solve();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
//freop();
int t=1; //cin >> t;
while (t--) process();
return 0;
}
