#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+"a.txt").c_str(),"w",stdout);
}
mt19937 rng;
int n,m;
int vis[301];
int vis3[301];
int vis2[501];
vector<int> adj[301];
int l;
int aa,bb;
set<pair<pair<int,int>,int>> cc;
int ans[301];
pair<int,int> loc[301];
pair<int,int> loc2[501];
int sect(int ac,int bc,int cc,int dc){
if(min(loc2[ac].a,loc2[bc].a)<=min(loc2[cc].a,loc2[dc].a) and min(loc2[cc].a,loc2[dc].a)<=max(loc2[ac].a,loc2[bc].a) and max(loc2[ac].a,loc2[bc].a) <=max(loc2[cc].a,loc2[dc].a)){
if(min(loc2[ac].b,loc2[bc].b)<=min(loc2[cc].b,loc2[dc].b) and min(loc2[cc].b,loc2[dc].b)<=max(loc2[ac].b,loc2[bc].b) and max(loc2[ac].b,loc2[bc].b) <=max(loc2[cc].b,loc2[dc].b)){
return 1;
}
else if(max(loc2[ac].b,loc2[bc].b)>=max(loc2[cc].b,loc2[dc].b) and max(loc2[cc].b,loc2[dc].b)>=min(loc2[ac].b,loc2[bc].b) and min(loc2[ac].b,loc2[bc].b) >=min(loc2[cc].b,loc2[dc].b)){
return 1;
}
else{
return 0;
}
}
else if(max(loc2[ac].a,loc2[bc].a)>=max(loc2[cc].a,loc2[dc].a) and max(loc2[cc].a,loc2[dc].a)>=min(loc2[ac].a,loc2[bc].a) and min(loc2[ac].a,loc2[bc].a) >=min(loc2[cc].a,loc2[dc].a)){
if(min(loc2[ac].b,loc2[bc].b)<=min(loc2[cc].b,loc2[dc].b) and min(loc2[cc].b,loc2[dc].b)<=max(loc2[ac].b,loc2[bc].b) and max(loc2[ac].b,loc2[bc].b) <=max(loc2[cc].b,loc2[dc].b)){
return 1;
}
else if(max(loc2[ac].b,loc2[bc].b)>=max(loc2[cc].b,loc2[dc].b) and max(loc2[cc].b,loc2[dc].b)>=min(loc2[ac].b,loc2[bc].b) and min(loc2[ac].b,loc2[bc].b) >=min(loc2[cc].b,loc2[dc].b)){
return 1;
}
else{
return 0;
}
}
else{
return 0;
}
}
bool cmp(int k,int l){
return loc2[k]<loc2[l];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(vis,0,sizeof(vis));
memset(vis2,0,sizeof(vis2));
memset(vis3,0,sizeof(vis3));
setIO("1");
rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>aa>>bb;
adj[aa-1].pb(bb-1);
adj[bb-1].pb(aa-1);
}
for(int i=0;i<n;i++){
shuffle(adj[i].begin(),adj[i].end(),rng);
}
cin>>l;
for(int i=0;i<l;i++){
cin>>aa>>bb;
loc2[i]={aa,bb};
}
vector<int> kk;
vector<int> ll;
/*for(int i=0;i<n;i++){
kk.pb(i);
}*/
for(int i=0;i<l;i++){
ll.pb(i);
}
sort(ll.begin(),ll.end(),cmp);
// shuffle(kk.begin(),kk.end(),rng);
// shuffle(ll.begin(),ll.end(),rng);
int tot2=0;
/*for(auto j:ll){
cout<<j<<":";
}
cout<<endl;*/
//vector<int> kk;
for(int i=0;i<1;i++){
int lo=rng()%n;
if(vis3[lo]==0){
vis3[lo]=1;
kk.pb(lo);
}
}
/*kk.pb(rng()%n);
vis3[kk[0]]=1;*/
vector<pair<int,int>> cur;
for(int i=0;i<n;i++){
pair<int,int> ans3={10000000,-1};
for(int j=0;j<l;j++){
if(vis2[ll[j]]==0){
int tot=0;
for(auto kko:adj[kk[i]]){
if(vis[kko]){
for(auto l:cur){
if(kko==l.a or kko==l.b){
continue;
}
// cout<<kk[i]<<','<<kko<<","<<l.a<<','<<l.b<<endl;
int ba=tot;
tot+=sect(ll[j],ans[kko],ans[l.a],ans[l.b]);
/*if(tot>ba){
cout<<ll[j]<<","<<ans[kko]<<","<<ans[l.a]<<","<<ans[l.b]<<endl;
}*/
}
}
}
if(tot<ans3.a){
ans3={tot,ll[j]};
}
}
}
tot2+=ans3.a;
vis[kk[i]]=1;
for(auto j:adj[kk[i]]){
if(vis[j]){
cur.pb({kk[i],j});
}
}
vis2[ans3.b]=1;
ans[kk[i]]=ans3.b;
// cout<<kk[i]<<","<<ans3.b<<","<<ans3.a<<endl;
for(auto j:adj[kk[i]]){
if(vis3[j]==0){
kk.pb(j);
vis3[j]=1;
}
}
}
// cout<<tot2<<endl;
set<int> ss;
int tot3=0;
for(auto i:cur){
for(int k=0;k<cur.size();k++){
pair<int,int> j=cur[k];
if(i.a==j.a or i.b==j.b or i.b==j.a or i.a==j.b){
}
else{
tot3+=sect(ans[i.a],ans[i.b],ans[j.a],ans[j.b]);
}
}
}
// cout<<tot3<<endl;
for(int i=0;i<n;i++){
cout<<ans[i]+1<<endl;
}
return 0;
}
