#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<pair<pair<int,int>,int>> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i].first.first >> d[i].first.second;
        d[i].second = i;
    }
    sort(d.begin(), d.end());
    vector<int> idx(n), inv(n);
    for (int i = 0; i < n; ++i) {
        idx[i] = d[i].second;
        inv[d[i].second] = i;
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int x,y; cin >> x >> y;
        x--; y--;
        x = inv[x], y = inv[y];
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> col(n,-1);
    for (int i = 0; i < n; ++i) {
        int bit = 0;
        vector<int> v;
        for(int j:g[i]){
            if(col[j] != -1){
                bit |= (1<<col[j]);
                v.push_back(j);
            }
        }
        // 使ってない色が存在する
        if(bit != 15){
            for (int j = 0; j < 4; ++j) {
                if((1<<j) & bit) continue;
                col[i] = j; break;
            }
        }
        else{
//            sort(v.begin(), v.end());
            {
                vector<int> nv;
                // 0
                for(int j:v){
                    if(d[i].first.second > d[j].first.second and d[j].first.first < d[i].first.first){
                        nv.push_back(j);
                    }
                }
                // 1
                for(int j:v){
                    if(d[i].first.second == d[j].first.second and d[j].first.first < d[i].first.first){
                        nv.push_back(j);
                    }
                }
                // 2
                for(int j:v){
                    if(d[i].first.second < d[j].first.second and d[j].first.first < d[i].first.first){
                        nv.push_back(j);
                    }
                }
                // 4
                for(int j:v){
                    if(d[i].first.first == d[j].first.first){
                        nv.push_back(j);
                    }
                }
                swap(v, nv);
            }
            vector<bool> used(n);
            queue<int> q;
            vector<int> v0;
            q.push(v[0]); used[v[0]] = true;
            while (q.size()){
                int s = q.front(); q.pop();
                v0.push_back(s);
                for(int t:g[s]){
                    if(col[t] == col[v[0]] or col[t] == col[v[2]]){
                        if(!used[t]){
                            used[t] = true; q.push(t);
                        }
                    }
                }
            }
            if(!used[v[2]]){
                int c0 = col[v[0]];
                int c2 = col[v[2]];
                for(int s:v0){
                    assert(col[s] == c0 or col[s] == c2);
                    col[s] = c0+c2-col[s];
                }
                col[i] = c0;
            }
            else{
                vector<int> v1;
                q.push(v[1]); used[v[1]] = true;
                while (q.size()){
                    int s = q.front(); q.pop();
                    v1.push_back(s);
                    for(int t:g[s]){
                        if(col[t] == col[v[1]] or col[t] == col[v[3]]){
                            if(!used[t]){
                                used[t] = true; q.push(t);
                            }
                        }
                    }
                }

                int c1 = col[v[1]];
                int c3 = col[v[3]];
                for(int s:v1){
                    assert(col[s] == c1 or col[s] == c3);
                    col[s] = c1+c3-col[s];
                }
                col[i] = c1;
            }
        }
    }
    vector<int> res(n);
    for (int i = 0; i < n; ++i) {
        res[idx[i]] = col[i];
    }
    for (int i = 0; i < n; ++i) {
        cout << res[i]+1 << "\n";
    }
}