#include <bits/stdc++.h>
#include "validate.h"

using namespace std;

string tolower(string s){
    string res = "";
    for(auto ch : s){
        res += tolower(ch);
    }
    return res;
}

struct test_case{
    int n,m,k;
    vector<vector<int> > graph;
    vector<int> weights;

    test_case(int n, int m, int k): n(n), m(m), k(k){
        graph.assign(n, vector<int>());
        weights.assign(n, 0);
    }

    vector<int> distance(){
        priority_queue<pair<int,int> > pq;
        vector<bool> seen(n, 0);
        vector<int> answer(n, 2e9);
        answer[0] = weights[0];
        pq.push({0, 0});
        while(!pq.empty()){
            int i = pq.top().second;
            pq.pop();
            if(!seen[i]){
                seen[i] = 1;
                for(int c1 = 0; c1 < graph[i].size(); c1++){
                    int j = graph[i][c1];
                    if(answer[i] + weights[j] < answer[j]){
                        answer[j] = answer[i] + weights[j];
                        pq.push({-answer[j], j});
                    }
                }
            }
        }
        return answer;
    }

    string validate_message(string colors){
        if(colors.length() != n)return "invalid output length\n";
        int ones = 0;
        for(int c1 = 0; c1 < n; c1++){
            if(colors[c1] != 'S' && colors[c1] != 'N'){
                return "invalid character\n";
            }
            ones += (colors[c1] == 'N');
        }

        if(ones != k)return "number of N:s not equal to k\n";

        vector<int> dist = distance();
        vector<pair<int,int> > top_sort;
        for(int c1 = 0; c1 < n; c1++){
            top_sort.push_back({dist[c1], c1});
        }
        sort(top_sort.begin(), top_sort.end());

        vector<bool> alternating(n, 0);
        alternating[0] = 1;

        for(int c1 = 0; c1 < n; c1++){
            int i = top_sort[c1].second;
            for(int c2 = 0; c2 < graph[i].size(); c2++){
                int j = graph[i][c2];
                if(dist[j] - dist[i] == weights[j] && alternating[i] && colors[i] != colors[j]){
                    alternating[j] = 1;
                }
            }
        }

        if(alternating[n-1])return "an alternating shortest path existed\n";

        return "ok";
    }
};

void check_case(){
    int n,m,k;

    judge_in >> n >> m >> k;
    test_case tc(n, m, k);

    for(int c1 = 0; c1 < n; c1++){
        judge_in >> tc.weights[c1];
    }
    for(int c1 = 0; c1 < m; c1++){
        int u, v;
        judge_in >> u >> v;
        u--;
        v--;
        tc.graph[u].push_back(v);
        tc.graph[v].push_back(u);
    }

    string author_answer, judge_answer;

    if(!(author_out >> author_answer)){
        wrong_answer("Could not read output\n");
    }
    if(!(judge_ans >> judge_answer)){
        judge_error("Could not read judge output\n");
    }

    if(tolower(author_answer) == "impossible"){
        if(tolower(judge_answer) == "impossible"){
            return;
        }
        wrong_answer("Output was 'impossible', but judge found a solution\n");
    }

    string author_validation = tc.validate_message(author_answer);
    string judge_validation = tc.validate_message(judge_answer);

    if(author_validation == "ok"){
        if(judge_validation != "ok"){
            judge_error("Contestant found a solution but judge did not\n");
        }
        return;
    }

    wrong_answer(author_validation);
}

int main(int argc, char **argv) {
  init_io(argc, argv);
  check_case();

  /* Check for trailing output. */
  string trash;
  if (author_out >> trash) {
      wrong_answer("Trailing output\n");
  }

  accept();
  return 0;
}