prj.cpp

/* Rozwiazanie zadania Nawiasy
 * Autor: Jacek Królikowski
 * Data: 30.09.2008
 */
//poprawiam repo
//
//
//
//cd
//#include <cstdio>
#include <ios>
#include <iostream>
#include <algorithm>
#include <climits>
#include <utility>
#include <limits>
//#include <set>
//#include <cstring>
#include <vector>
#include <cassert>
typedef long int myint;
typedef long int progint;
using namespace std;

const myint MAX_N = 100000;
const myint MAX_M = 500000;
const myint MAX_K = MAX_N;
const progint MAX_P = 100000000;

class Projekt;
Projekt* projects[MAX_N+1];
Projekt* sorted[MAX_N+1];

myint n,k,m;


class Projekt{
	public: //tak, az taki jestem leniwy
		myint no;
		bool visited, is_leaf;
		vector<Projekt*> parents;
		progint p;
		progint tru_p;
	//public:
		Projekt(myint inno, progint pin){
			no = inno;
			visited = false;
			is_leaf = true;
			parents.clear();
			p = pin;
			tru_p = pin;
			//projects[no] = this;
		}

		void setMe(Projekt* inarr[]){
			inarr[no] = this;
		}
		void innerVisit(progint pin, bool force){
			bool changed = false;
			if(tru_p < pin){
				tru_p = pin;
				changed = true;
			}
			if (changed || (force && !visited)){
				visited = true;
				vector<Projekt*>::iterator it;
				Projekt* tmproj;
				for(it = parents.begin(); it < parents.end(); it++){
					tmproj = *it;
					tmproj->innerVisit(tru_p, force);	
				}
			}
			
		}
		void visit(bool force){
			visited = true;
			vector<Projekt*>::iterator it;
			Projekt* tmproj;
			for(it = parents.begin(); it < parents.end(); it++){
				tmproj = *it;
				tmproj->innerVisit(tru_p, force);	
			}
		}
};
/* funkcje */

void _return(myint ret){
	cout << ret;
	exit(0);
}


bool trusort(Projekt *i, Projekt *j){
	return i->tru_p < j->tru_p;
}

void wypisz(Projekt *c){
	cout << "nr: " << c->no << " p: " << c->p << " tru_p: " << c->tru_p << endl;
	
}
void wypiszWszystkie(Projekt* inarr[]){
	for (myint i=1; i<=n; i++){
		wypisz(inarr[i]);
	}
}

void sort(){
	std::sort(sorted+1, sorted+n+1, trusort);
}
	
int main() {
	/* To sie przydaje */
	ios_base::sync_with_stdio(0);
	assert(MAX_P < LONG_MAX);
	assert(MAX_M < LONG_MAX);
	
	cin >> n >> m >> k;
	myint tmp;
	for(myint i = 1; i<=n; i++){

		cin >> tmp;
		projects[i] = new Projekt(i, tmp);	
		sorted[i] = projects[i];
	}
	myint from, to;
	for(myint i=0; i < m; i++){
		cin >> to >> from;
		projects[to]->is_leaf = false;
		projects[from]->parents.push_back(projects[to]);
	}
	//cout << endl;
	//std::sort(zs, zs+n, zsort);
	//wypiszWszystkie(sorted);
	sort();
   //cout << "posortowane" << endl;
	
	//wypiszWszystkie(sorted);

	//przerabianie
	for(myint i=n; i>0; i--){
		if (sorted[i]->is_leaf){
			sorted[i]->visit(true);	
		}
	}
	//cout << "przeszedlem je wszystkie" << endl;
	sort();
	//wypiszWszystkie(sorted);
	
	//okreslamy wynik
	cout << sorted[k]->tru_p;
	return 0;
}