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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int n, m, a, b;
int pomiar[500005];
int ktory[500005];
int naco[500005];
int result[500005];

vector <int> v[500005];
vector <int>::iterator it;

int rozmiar;
vector <int> numery;

bool comp (int F, int S)
{
	for (int i = 0; i < rozmiar; ++i)
	{
		int kk = numery[i];
		if (F < v[kk][0]) a = pomiar[kk];
		else
		{
			it = upper_bound(v[kk].begin(), v[kk].end(), F);
			it--;
			a = naco[*it];
		}
		if (S < v[kk][0]) b = pomiar[kk];
		else
		{
			it = upper_bound(v[kk].begin(), v[kk].end(), S);
			it--;
			b = naco[*it];
		}
		if (a < b) return 1;
		if (a > b) return 0;
	}
	return F < S;
}

int main ()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &pomiar[i]);
	for (int i = 2; i <= m; ++i)
	{
		scanf("%d%d", &ktory[i], &naco[i]);
		v[ktory[i]].push_back(i);
	}
	for (int i = 1; i <= n; ++i) if (!v[i].empty()) numery.push_back(i);
	rozmiar = numery.size();
	for (int i = 0; i < m; ++i) result[i] = i + 1;
	sort(result, result + m, comp);
	for (int i = 0; i < m; ++i) printf("%d ", result[i]);
	printf("\n");
	return 0;
}