#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define pii pair<long long,long long>
#define mii map<string,long long>
using namespace std;
vector < vector < long long > > d(200005);
long long color[200005];
bool danhdau[200005];
class solution
{
public:
long long n,m,t;
const long long nmax=1e6 + 5;
mii mymap;
vector < string > data;
vector < long long > deg;
vector < long long > col;
vector < long long > color_avai;
void init()
{
for(long long i = 0 ; i < 200000 ; i++) d[i].clear();
deg.resize(nmax);
for(long long i = 0 ; i < n ; i++) deg[i] = 0;
}
void in()
{
cin >> m >> n ;
t = m;
for(long long i = 0 ; i < m ; i++)
{
string x;
cin >> x;
data.pb(x);
mymap[x] = i+1;
}
for(long long i = 0 ; i < n ; i++)
{
string x;
cin >> x;
string y;
cin >> y;
d[mymap[x]].pb(mymap[y]);
d[mymap[y]].pb(mymap[x]);
deg[mymap[x]]++;
deg[mymap[y]]++;
}
for(long long i = 1 ; i <= m ; i++)
{
set<long long> colo(d[i].begin(),d[i].end());
vector<long long> s1(colo.begin(),colo.end());
d[i] = s1;
deg[i] = d[i].size();
}
for(long long i = 0 ; i < n ; i++) color[i] = -1;
for(long long i = 0 ; i < n ; i++) danhdau[i] = false;
//cout << endl;
color_avai.clear();
// for(long long i = 1 ; i <= m; i++) cout << deg[i] << " ";
// cout << endl;
//for(long long i = 0 ; i < color_avai.size(); i++) cout << color_avai[i] << " ";
//cout << endl;
}
string found()
{
long long val = LLONG_MIN, id = -1;
for(long long i = 1 ; i <= m ; i++)
{
if (deg[i] > val && danhdau[i] == false)
{
val = deg[i];
id = i;
}
}
//cout << data[id - 1] << endl;
if (id != -1)
{
deg[id] = -1;
danhdau[id] = true;
return data[id - 1];}
return "";
// for(int i = 0 ; i < d[id].size(); i++)
// {
// deg[d[id][i]]--;
// }
}
void solve()
{
while (t--)
{
//for(long long i = 1 ; i <= m ; i++) cout << deg[i] << " ";
//cout << endl;
set<long long> colo(color_avai.begin(),color_avai.end());
vector<long long> s1(colo.begin(),colo.end());
color_avai = s1;
string x = found();
if (x == "") break;
if (color[mymap[x]] == -1)
{
long long j,cnt = 0;
for(long long i = 0 ; i < color_avai.size(); i++)
if (color_avai[i] == i) cnt++;
else break;
for(j = 0 ; j < color_avai.size(); j++)
{
bool flag1 = true;
for(long long i = 0 ; i < d[mymap[x]].size(); i++)
{
if (color_avai[j] == color[d[mymap[x]][i]]) flag1 = false;
}
if (flag1 == true)
{
color[mymap[x]] = color_avai[j];
break;
}
}
if (j == color_avai.size())
{
color[mymap[x]] = cnt;
color_avai.pb(cnt);
}
}
else
{
long long j, cnt = 0;
for(long long i = 0 ; i < color_avai.size(); i++)
if (color_avai[i] == i) cnt++;
else break;
// cout << "Color available: " << color_avai.size() << endl;
// cout << cnt << endl;
bool flag = true;
for(long long i = 0 ; i < d[mymap[x]].size(); i++)
if (color[mymap[x]] == color[d[mymap[x]][i]])
{
flag = false;
break;
}
if (flag == false) {
for(j = 0 ; j < color_avai.size(); j++)
{
bool flag1 = true;
for(long long i = 0 ; i < d[mymap[x]].size(); i++)
{
if (color_avai[j] == color[d[mymap[x]][i]]) flag1 = false;
}
if (flag1 == true)
{
color[mymap[x]] = color_avai[j];
break;
}
}
if (j == color_avai.size())
{
color[mymap[x]] = cnt;
color_avai.pb(cnt);
}
}
}
}
}
void out()
{
for(long long i = 1 ; i <= m ; i++) cout << color[i] << " ";
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solution *sol = new solution;
sol->init();
sol->in();
sol->solve();
sol->out();
return 0;
}