#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

struct unionfind
{
    vector<long long> d;

    unionfind(long long n) : d(n, -1) {}

    long long root(long long x)
    {
        if (d[x] < 0)
        {
            return x;
        }
        else
        {
            return d[x] = root(d[x]);
        }
    }

    bool unite(long long x, long long y)
    {
        x = root(x);
        y = root(y);

        if (x == y)
        {
            return false;
        }

        if (d[x] > d[y])
        {
            swap(x, y);
        }

        d[x] += d[y];
        d[y] = x;
        return true;
    }

    bool same(long long x, long long y)
    {
        return root(x) == root(y);
    }

    long long size(long long x)
    {
        return -d[root(x)];
    }
};

int main(void)
{
    ll n, m;

    cin >> n >> m;

    vector<ll> a(m), b(m);
    vector<vector<ll>> g(n, vector<ll>());

    for (int i = 0; i < m; i++)
    {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;

        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }

    ll k;
    cin >> k;

    vector<vector<ll>> g_d(k, vector<ll>(k, INF));
    vector<ll> c(k);

    for (int i = 0; i < k; i++)
    {
        cin >> c[i];
        c[i]--;
    }

    for (int i = 0; i < k; i++)
    {
        queue<ll> q;
        q.push(c[i]);

        vector<ll> dis(n, INF);
        dis[c[i]] = 0;

        while (q.size())
        {
            ll p = q.front();
            q.pop();

            for (auto &&x : g[p])
            {
                if (dis[x] == INF)
                {
                    dis[x] = dis[p] + 1, dis[x];
                    q.push(x);
                }
            }
        }

        for (int j = 0; j < k; j++)
        {
            if (i == j)
            {
                g_d[i][j] = 0;
                g_d[j][i] = 0;
            }

            if (dis[c[j]] == INF)
            {
                cout << -1 << endl;
                return 0;
            }

            ll d;
            d = min(g_d[i][j], dis[c[j]]);

            g_d[i][j] = d;
            g_d[j][i] = d;
        }
    }

    ll maxd = 0;
    bool flag = false;

    for (int i = 0; i < k; i++)
    {
        for (int j = i + 1; j < k; j++)
        {
            maxd = max(maxd, g_d[i][j]);
        }
    }

    // for (int i = 0; i < k; i++)
    // {
    //     for (int j = 0; j < k; j++)
    //     {
    //         printf("%lld ", g_d[i][j]);
    //     }
    //     printf("\n");
    // }

    vector<vector<ll>> dp(1 << k, vector<ll>(k, INF));

    for (int i = 0; i < k; i++)
    {
        dp[1 << i][i] = 1;
    }

    for (int bit = 1; bit < 1 << k; bit++)
    {
        for (int i = 0; i < k; i++)
        {
            for (int j = 0; j < k; j++)
            {
                dp[bit | 1 << j][j] = min(dp[bit | 1 << j][j], dp[bit][i] + g_d[i][j]);
            }
        }
    }

    ll ans = INF;

    for (int i = 0; i < k; i++)
    {
        ans = min(ans, dp[(1 << k) - 1][i]);
    }

    cout << ans << endl;
}

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    int N,K;
    cin>>N>>K;
    vector<vector<int>> A(N,vector<int>(N));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>A[i][j];
        }
    }
    vector<int> kouho;
    int left=-1,right=1e9+1;
    while(right-left>1){
        int mid=(right-left)/2+left;
        vector<vector<int>> a(N,vector<int>(N)),sum(N,vector<int>(N));
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(A[i][j]>mid) a[i][j]=1;
                else a[i][j]=0;
            }
        }
        sum[0][0]=a[0][0];
        for(int i=1;i<N;i++) sum[i][0]=sum[i-1][0]+a[i][0];
        for(int i=1;i<N;i++) sum[0][i]=sum[0][i-1]+a[0][i];
        for(int i=1;i<N;i++){
            for(int j=1;j<N;j++){
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
            }
        }
        bool f=false;
        if(sum[K-1][K-1]<=K*K/2) f=true;
        for(int i=1;i<=N-K;i++){
            if(sum[i+K-1][K-1]-sum[i-1][K-1]<=K*K/2) f=true;
        }
        for(int i=1;i<=N-K;i++){
            if(sum[K-1][i+K-1]-sum[K-1][i-1]<=K*K/2) f=true;
        }
        for(int i=1;i<=N-K;i++){
            for(int j=1;j<=N-K;j++){
                if(sum[i+K-1][j+K-1]-sum[i-1][j+K-1]-sum[i+K-1][j-1]+sum[i-1][j-1]<=K*K/2){
                    f=true;
                }
            }
        }
        if(f){
            right=mid;
        }else{
            left=mid;
        }
    }
    cout<<right<<endl;
    return 0;
}