// cre: Nguyen Ngoc Hung - Go Go VOI 2024 :>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
#include <chrono>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define PB push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j)
#define REPD(i,be,en) for(int i = (be); i>=(en); --i)
#define REP(i,be,en) for(int i = (be); i<=(en); ++i)
#define endl "\n"
#define int ll
//------------------------------------------------------------------------------------------------//
int readInt(){
char c;
do{ c = getchar(); }while(c!='-' && !isdigit(c));
bool neg = (c=='-');
int res = neg?0:c-'0';
while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 5e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
const ld EPS = 1e-9,PI = acos(-1);
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
struct DSU{
vi par;
int n;
int find(int u){
return u==par[u]?u:par[u]=find(par[u]);
}
bool same(int u, int v){
return find(u)==find(v);
}
bool unite(int u, int v){
u = find(u); v = find(v);
if(u==v) return false;
par[v] = u;
return true;
}
DSU(int _n):n(_n){
par.resize(n+3);
iota(ALL(par),0);
}
};
struct edge{
int u,v,w,id;
bool operator < (const edge &other) const {
return w<other.w;
}
};
int ok[MAXN],vis[MAXN],s[MAXN],h[MAXN],p[MAXN],pe[MAXN],t[MAXN];
vector<edge> edges;
vpii adj[MAXN];
vi now,nho;
int n,m;
int find(int u){
return s[u]<0?u:s[u]=find(s[u]);
}
void unite(int u, int v){
if(s[u]>s[v]) swap(u,v);
if(u!=v){
if(h[t[u]]>h[t[v]]) t[u] = t[v];
s[u] += s[v];
s[v] = u;
}
}
void dfs(int u, int par, int dep, int e){
h[u] = dep;
p[u] = par;
pe[u] = e;
for(auto &[v,id]:adj[u]){
if(v==par) continue;
dfs(v,u,dep+1,id);
}
}
void sub1(){
vi perm(m),res(m); iota(ALL(perm),0); iota(ALL(res),n);
do{
vector<edge> now = edges;
REP(i,0,m-1) now[i].w = perm[i]+1;
sort(ALL(now));
DSU dsu(n);
int flag = 1;
REP(i,0,m-1){
if(dsu.unite(now[i].u,now[i].v)){
if(ok[now[i].id]==0){
flag = 0;
break;
}
}
}
if(flag) mini(res,perm);
}while(next_permutation(ALL(perm)));
for(auto &i:res) cout << i+1 << " ";
}
void sub5(){
int cnt = 0;
vi res;
REP(i,1,m){
if(ok[i]==0){
res.push_back(m);
continue;
}
res.push_back(++cnt);
}
for(auto &i:res) cout << i << " ";
}
void sub7(){
dfs(1,0,0,0);
REP(i,1,n){
s[i] = -1;
t[i] = i;
}
vi res(m+1,0);
int j = 1;
REP(i,1,m){
int u = find(edges[i-1].u),v = find(edges[i-1].v);
if(ok[i]==1 && res[i]==0){
res[i] = j++;
unite(u,v);
}
if(res[i]!=0) continue;
// edge i - not mst
vi tmp;
while(u!=v){
if(h[t[u]]<h[t[v]]) swap(u,v);
tmp.push_back(pe[t[u]]);
unite(u,find(p[t[u]]));
u = find(u); v = find(v);
}
sort(ALL(tmp));
for(auto &x:tmp) res[x] = j++;
res[i] = j++;
}
REP(i,1,m) cout << res[i] << " ";
}
/*
6 6
1 4
1 2
2 3
4 5
3 4
5 6
2 3 4 5 6
*/
void solve(){
cin >> n >> m;
int s5 = 1;
REP(i,1,m){
int u,v; cin >> u >> v;
edges.push_back({u,v,0,i});
if(u!=i || v!=i%n+1) s5 = 0;
}
REP(i,1,n-1){
int x; cin >> x;
ok[x] = 1;
adj[edges[x-1].u].emplace_back(edges[x-1].v,x);
adj[edges[x-1].v].emplace_back(edges[x-1].u,x);
}
// sub7(); return ;
if(n<=9 && m<=9){
sub1();
return ;
}
if(s5 && n==m){
sub5();
return ;
}
sub7();
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "test"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
#define task1 "ZONING"
if(fopen(task1".inp","r")){
freopen(task1".inp","r",stdin);
freopen(task1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
/** /\_/\
* (= ._.)
* / >TL \>AC
**/
