#include <iostream>
#include <iomanip>
#include <algorithm>
#include <assert.h>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=a;i<b;++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,a) rrepi(i,a,0)
#define rrepi(i,a,b) for(ll i=a-1;i>=b;--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}

const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1e6;
const ll EPS = 1e-10;
int sgn(const double a){
    return (a < -EPS ? -1 : (a > EPS ? +1 : 0));
}
typedef pair<int,int> pi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> tri;
typedef pair<double,double> point;
typedef complex<double> Point;
const ll MAX = 1000005;
constexpr ll nx[4] = {-1,0,1,0};
constexpr ll ny[4] = {0,1,0,-1};

ll m; //m次正方行列
vector<ll> matmul(vector<ll> &dp,vector<vector<ll>> &mt){
    vector<ll> ret(m,0);
    rep(i,m) rep(j,m) (ret[i] += mt[i][j]*dp[j]%MOD)%=MOD;
    return ret;
}
vector<vector<ll>> update(vector<vector<ll>> &mt){
    vector<vector<ll>> ret(m,vector<ll>(m,0));
    rep(i,m) rep(j,m) rep(k,m) (ret[i][j] += mt[i][k]*mt[k][j]%MOD)%=MOD;
    return ret;
}
void matpow(vector<ll> &dp,vector<vector<ll>> &mt,ll k){
    m = dp.size();
    while(k){
        if(k&1) dp = matmul(dp,mt);
        mt = update(mt);
        k /= 2; 
    }
}

ll mod_pow(ll n, ll p, ll m){
    ll ret = 1;
    ll mul = n%m;
    while(p){
        if (p&1) ret = ret*mul%m;
        p >>= 1;
        mul = mul*mul%m;
    }
    return ret;
}

class Combination{
    public:
    ll MAX,M;
    vector<ll> fac,finv,inv;
    Combination(ll MAX_,ll MOD_):MAX(MAX_),M(MOD_){
        fac.resize(MAX);
        finv.resize(MAX);
        inv.resize(MAX);
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        rep(i,2,MAX){
            fac[i] = fac[i-1]*i%M;
            inv[i] = M-inv[M%i]*(M/i)%M;
            finv[i] = finv[i-1]*inv[i]%M;
        }
    }

    ll COM(ll n,ll k){
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n]*(finv[k]*finv[n-k]%M)%M;
    }
};

int main(){
    Combination com(100000,MOD);
    ll n,k; //edge
    cin >> m >> n >> k;
    vector<ll> a(m);
    cins(all(a));
    vector<vector<ll>> mat(m,vector<ll>(m,0)),g(m);
    rep(i,m) mat[i][i] = n;
    rep(i,n){
        ll x,y;
        cin >> x >> y;
        x--,y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    rep(i,m){
        ll cnt = 0;
        for (ll v:g[i]){
            mat[i][v]++;
            cnt++;
        }
        mat[i][i] += n-cnt;
    }
    rep(i,m){
        //array_output(all(mat[i]));
    }
    ll re = com.inv[2*n],mul = mod_pow(re,k,MOD);
    matpow(a,mat,k);
    rep(i,m){
        PRINT(a[i]*mul%MOD);
    }
}

#include <bits/stdc++.h>
using namespace std;
#define reps(i, a, n) for (int i = (a); i < (n); ++i)
#define rep(i, n) reps(i, 0, n)
#define deps(i, a, n) for (int i = (a); i >= (n); --i)
#define dep(i, n) deps(i, n, 0)
#define inf 2147483647
#define int long long

int n, m;
int a[105], b[105];
int k;
int c[20], d[20];
int ans = 0;

void func(int i, int s[])
{
	int ans2 = 0;
	rep (j, m)
	{
		if (s[a[j]] >= 1 && s[b[j]] >= 1) ans2++;
	}
	ans = max(ans, ans2);

	if (i >= k) return;

	s[c[i]]++;
	func(i + 1, s);
	s[c[i]]--;

	s[d[i]]++;
	func(i + 1, s);
	s[d[i]]--;
}

signed main(void)
{
	cin >> n >> m;
	rep (i, m) cin >> a[i] >> b[i];
	cin >> k;
	rep (i, k) cin >> c[i] >> d[i];
	int s[105] = {0};
	func(0, s);
	cout << ans << endl;
}
