#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 100005;
vector<int> graph[maxn];

struct node {
    int idx, passed_cities, quality;
    node () {}
    node(int _idx, int _passed_cities, int _quality) {
        idx = _idx;
        passed_cities = _passed_cities;
        quality = _quality;
    }
    bool operator < (const node & tmp) const {
        int score1 = 0, score2 = 0;
        if(quality > tmp.quality) {
            score1++;
        }
        else {
            score2++;
        }

        if(passed_cities < tmp.passed_cities) {
            score1++;
        }
        else {
            score2++;
        }
        return score1 < score2;
    }
};
int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> quality(n);
    for(int i = 0; i < n; i++) {
        cin >> quality[i];
    }

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    priority_queue<node> pq;
    pq.push(node(0, 1, quality[0]));
    vector<bool> visited(n, false);
    vector<int> dist(n, -2e9);
    int res_quality = -2e9, res_passed_cities = 2e9;
    while(!pq.empty()) {
        node c = pq.top();
        pq.pop();

        if(c.idx == n - 1) {
            if(c.quality > res_quality) {
                res_quality = c.quality;
                res_passed_cities = c.passed_cities;
            }
            else if(c.quality == res_quality) {
                if(res_passed_cities > c.passed_cities) {
                    res_passed_cities = c.passed_cities;
                }
            }
            continue;
        }

        for(int i = 0; i < (int) graph[c.idx].size(); i++) {
            int neighbour = graph[c.idx][i];
            if(c.passed_cities < k and dist[neighbour] < min(c.quality, quality[neighbour])) {
                dist[neighbour] = min(c.quality, quality[neighbour]);
                pq.push(node(neighbour, c.passed_cities + 1, dist[neighbour]));
            }
        }
    }
    cout << res_quality << " " << res_passed_cities << endl;

    return 0;
}