1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// Artur Kraska, II UWr

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cmath>
#include <list>
#include <set>
#include <map>

#define forr(i, n)                  for(int i=0; i<n; i++)
#define FOREACH(iter, coll)         for(auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll)        for(auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P,R,PRED)            ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;})
#define testy()                     int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests)
#define CLEAR(tab)                  memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll)           (coll.find(el) != coll.end())
#define FOR(i, a, b)                for(int i=a; i<=b; i++)
#define FORD(i, a, b)               for(int i=a; i>=b; i--)
#define MP                          make_pair
#define PB                          push_back
#define deb(X)                      X;

#define M 1000000007
#define INF 1000000007

using namespace std;

int n, m, tab[1000007], a, b, num[1000007];
map <int, int> mapa;
vector <pair<int, int> > v[1000007];
vector <int> kubelek[1000007], l;
set <int> S;

int main()
{
    scanf("%d %d", &n, &m);
    forr(i, n)
    {
        scanf("%d", &tab[i]);
        mapa[tab[i]] = 1;
    }
    FOR(i, 2, m)
    {
        scanf("%d %d", &a, &b);
        a--;
        mapa[b] = 1;
        v[a].PB(MP(i, b));
    }

    int nn = 0;
    FOREACH(it, mapa)
    {
        it->second = ++nn;
    }
    forr(i, n)
    {
        tab[i] = mapa[tab[i]];
        FOREACH(it, v[i])
            it->second = mapa[it->second];
    }

    FOR(i, 1, m)
        l.PB(i);

    FORD(i, n-1, 0)
    {
        if(v[i].size() == 0)
            continue;

        int poz = 0, teraz = tab[i];
        S.clear();

        num[1] = teraz;
        S.insert(teraz);
        FOR(j, 2, m)
        {
            if(poz < v[i].size() && v[i][poz].first == j)
            {
                teraz = v[i][poz].second;
                S.insert(teraz);
                poz++;
            }
            num[j] = teraz;
        }

        FOREACH(it, l)
        {
            kubelek[num[*it]].PB(*it);
        }
        l.clear();

        FOREACH(it, S)
        {
            FOREACH(it2, kubelek[*it])
                l.PB(*it2);
            kubelek[*it].clear();
        }
        /*
        cout << "po iteracji " << i << ": ";
        FOREACH(it, l)
            printf("%d ", *it);
        printf("\n");
        */
    }

    FOREACH(it, l)
        printf("%d ", *it);
    printf("\n");

    return 0;
}