#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
using namespace::std;

const int N = 25, M = 1024 * 1024 + 5;
vector<int> t[N];
bitset<32> q;
int n, m, dp[M], wyn[M], pot[N], ile;
bool o[M], o2[M];

void zrob(int index) {
    q = index;
    o[index] = true;
    for (int i = 0; i < n; i++)
        if (!o[index | pot[i]]) {
            int biale = 0;
            for (int w : t[i + 1])
                if (q[w - 1] == 0) biale++;
            dp[index | pot[i]] = dp[index] + 2 * biale - t[i + 1].size();
        }
}

void wylicz(int index) {
    q = index;
    o2[index] = true;
    wyn[index] = dp[index];
    for (int i = 0; i < n; i++)
        if (q[i] == 1) wyn[index] = max(wyn[index], wyn[index ^ pot[i]]);
}

int liczba(string &s) {
    int rez = 0, mnoz = 1;
    for (int i = 0; i < s.size(); i++) {
        rez += (s[i] - '0') * mnoz;
        mnoz <<= 1;
    }
    return rez;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> ile;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        t[a].push_back(b);
        t[b].push_back(a);
    }
    int s = 1;
    for (int i = 0; i < n; i++) {
        pot[i] = s;
        s *= 2;
    }
    for (int i = 0; i < pow(2, n); i++) {
        if (!o[i]) zrob(i);
        if (!o2[i]) wylicz(i);
    }
    for (int i = 0; i < ile; i++) {
        string s;
        cin >> s;
        cout << wyn[liczba(s)]<< endl;
    }
}