#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

#define MaxN 2000

int n, m, best, sol;
int a [MaxN][MaxN];
int p [MaxN], q [MaxN], deg [MaxN];

void input (char* file)
{
    int x, y;

    ifstream in (file);
    in >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a [i][j] = 0;
    for (int i = 1; i <= n; i++)
        deg [i] = 0;
    for (int i = 1; i <= m; i++)
    {
        in >> x >> y;
        deg [x]++;
        a [x][deg [x]] = y;
        deg [y]++;
        a [y][deg [y]] = x;
    }
    in.close();
}

void output (char* file)
{
    int x, y;

    ifstream out (file);
    out >> best;
    for (int i = 1; i <= n; i++)
            out >> p [i];
    out.close();
}

int calc (int p [], int q [])
{
    int sum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= deg [p [i]]; j++)
            sum += abs (i - q [a [p [i]][j]]);
    return sum / 2;
}

int check (char *file)
{
    int x, y;
    char line[100];

    ifstream out (file);
    out.getline(line, 100);

    out >> sol;
    for (int i = 1; i <= n; i++)
        q [i] = 0;
    for (int i = 1; i <= n; i++)
    {
        out >> p [i];
        if ((p [i] <= 0) || (p [i] > n) || (q [p [i]] != 0))
        {
             out.close();
             return 0;
        }
        q [p [i]] = i;
    }
    out.close();
    if (sol != calc(p, q))
         return 0;
  int k = 3;
    double tmp = (k - ((double)sol) / ((double)best)) / ((double)(k - 1));
    return (int)(pow (10.0, tmp) + 1.0 - 1e-8);
}

int main (int argc, char **argv)
{
//  input ("bandere.in");
//  output ("bandere.sol");
//  cout << check ("bandere.out") << endl;
  input (argv [1]);
  output (argv [3]);
  cout << check (argv [2]) << endl;
    return 0;
}