#include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=3e5+5; int n, m, sz[nx], par[nx], cur=0, ans[nx], h[nx], nod[nx<<2]; int top[nx], chain=0, id[nx], pos[nx], tim=0, st[nx<<2], mn[nx<<2]; vector<int> adj[nx], ve; vector<ii> rem; ii ed[nx]; bool in[nx], la[nx<<2], ok[nx]; void dfs(int u) { sz[u]=1; for(int v:adj[u]) { if(v==par[u]) continue; par[v]=u; h[v]=h[u]+1; dfs(v); sz[u]+=sz[v]; } } void hld(int u) { if(!top[chain]) top[chain]=u; id[u]=chain; pos[u]=++tim; int sp=-1; for(int v:adj[u]) if(v!=par[u]) if(sp==-1 || sz[v]>sz[sp]) sp=v; if(sp!=-1) hld(sp); for(int v:adj[u]) if(v!=par[u] && v!=sp) chain++, hld(v); } void build(int id, int l, int r) { mn[id]=inf; la[id]=0; if(l==r) { nod[id]=1; st[id]=inf; return; } int mid=(l+r)>>1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); nod[id]=nod[id<<1]+nod[id<<1|1]; st[id]=min(st[id<<1], st[id<<1|1]); } void down(int id) { if(la[id]) { for(int j = id*2; j <= id*2+1; j++) nod[j]=0, la[j]=1; la[id]=0; } if(mn[id]<inf) { for(int j = id*2; j <= id*2+1; j++) st[j]=min(st[j], mn[id]), mn[j]=min(mn[j], mn[id]); mn[id]=inf; } } void update(int id, int l, int r, int u, int v) { if(l>v || r<u) return; if(l>=u && r<=v) { la[id]=1; nod[id]=0; return; } int mid=(l+r)>>1; down(id); update(id<<1, l, mid, u, v); update(id<<1|1, mid+1, r, u, v); nod[id]=nod[id<<1]+nod[id<<1|1]; st[id]=min(st[id<<1], st[id<<1|1]); } void upd(int id, int l, int r, int u, int v, int val) { if(l>v || r<u) return; if(l>=u && r<=v) { st[id]=min(st[id], val); mn[id]=min(mn[id], val); return; } int mid=(l+r)>>1; down(id); upd(id<<1, l, mid, u, v, val); upd(id<<1|1, mid+1, r, u, v, val); nod[id]=nod[id<<1]+nod[id<<1|1]; st[id]=min(st[id<<1], st[id<<1|1]); } int get(int id, int l, int r, int u, int v) { if(l>v || r<u) return 0; if(l>=u && r<=v) return nod[id]; int mid=(l+r)>>1; down(id); return get(id<<1, l, mid, u, v)+get(id<<1|1, mid+1, r, u, v); } int getpath(int u, int v) { int ha=0; while(id[u]!=id[v]) { int cu=id[u], cv=id[v]; if(h[top[cu]]<h[top[cv]]) swap(u, v), swap(cu, cv); ha+=get(1, 1, n, pos[top[cu]], pos[u]); u=par[top[cu]]; } if(h[u]<h[v]) swap(u, v); ha+=get(1, 1, n, pos[v]+1, pos[u]); return ha; } void solve(int u, int v, int val) { while(id[u]!=id[v]) { int cu=id[u], cv=id[v]; if(h[top[cu]]<h[top[cv]]) swap(u, v), swap(cu, cv); update(1, 1, n, pos[top[cu]], pos[u]); upd(1, 1, n, pos[top[cu]], pos[u], val); u=par[top[cu]]; } if(h[u]<h[v]) swap(u, v); update(1, 1, n, pos[v]+1, pos[u]); upd(1, 1, n, pos[v]+1, pos[u], val); } int getmin(int id, int l, int r, int p) { if(l>p || r<p) return inf; if(l==r) return st[id]; int mid=(l+r)>>1; down(id); return min(getmin(id<<1, l, mid, p), getmin(id<<1|1, mid+1, r, p)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i = 1; i <= m; i++) { int u, v; cin>>u>>v; ed[i]={u, v}; } for(int i = 1; i < n; i++) { int x; cin>>x; in[x]=1; int u, v; tie(u, v)=ed[x]; adj[u].emplace_back(v); adj[v].emplace_back(u); } dfs(1); hld(1); build(1, 1, n); for(int i = 1; i <= m; i++) { int u, v; tie(u, v)=ed[i]; if(par[v]==u) swap(ed[i].fi, ed[i].se); } for(int i = 1; i <= m; i++) { int u, v; tie(u, v)=ed[i]; if(in[i]) { if(get(1, 1, n, pos[u], pos[u])==1) ans[i]=++cur, update(1, 1, n, pos[u], pos[u]); continue; } int cnt=getpath(u, v); cur+=cnt; ans[i]=++cur; solve(u, v, cur); } for(int i = 1; i <= m; i++) ok[ans[i]]=1; for(int i = m; i >= 1; i--) if(!ok[i]) ve.emplace_back(i); for(int i = 1; i <= m; i++) { int u, v; tie(u, v)=ed[i]; if(ans[i]==0) rem.emplace_back(getmin(1, 1, n, pos[u]), i); } sort(rem.begin(), rem.end()); for(auto it:rem) ans[it.se]=ve.back(), ve.pop_back(); for(int i = 1; i <= m; i++) cout<<ans[i]<<' '; }