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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string mode;
    if (!(cin >> mode)) return 0;

    int t;
    if (!(cin >> t)) return 0;

    if (mode == "Kevin") {
        for (int tc = 1; tc <= t; tc++) {
            int n, m;
            cin >> n >> m;

            for (int i = 0; i < m; i++) {
                int u, v;
                cin >> u >> v;
            }

            vector<int> a(n + 1);
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
            }

            auto group = [&](int x) {
                return x >= 3; // colors 1,2 -> 0 ; colors 3,4 -> 1
            };

            vector<int> bits;

            int base = group(a[1]);

            for (int i = 2; i <= n; i++) {
                bits.push_back(group(a[i]) ^ base);
            }

            vector<int> msg;

            for (int i = 0; i < (int)bits.size(); i += 2) {
                int x = bits[i];

                if (i + 1 < (int)bits.size()) {
                    x += 2 * bits[i + 1];
                }

                msg.push_back(x + 1); // 0..3 -> 1..4
            }

            cout << msg.size() << '\n';

            for (int i = 0; i < (int)msg.size(); i++) {
                if (i) cout << ' ';
                cout << msg[i];
            }

            cout << '\n';
        }
    } else {
        for (int tc = 1; tc <= t; tc++) {
            int n, m;
            cin >> n >> m;

            vector<vector<int>> adj(n + 1);

            for (int i = 0; i < m; i++) {
                int u, v;
                cin >> u >> v;

                adj[u].push_back(v);
                adj[v].push_back(u);
            }

            int k;
            cin >> k;

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

            vector<int> side(n + 1, 0);

            int ptr = 2;

            for (int x : msg) {
                x--;

                if (ptr <= n) {
                    side[ptr] = x & 1;
                    ptr++;
                }

                if (ptr <= n) {
                    side[ptr] = (x >> 1) & 1;
                    ptr++;
                }
            }

            vector<int> parity(n + 1, -1);

            for (int s = 1; s <= n; s++) {
                if (parity[s] != -1) continue;

                parity[s] = 0;

                queue<int> q;
                q.push(s);

                while (!q.empty()) {
                    int u = q.front();
                    q.pop();

                    for (int v : adj[u]) {
                        if (side[u] != side[v]) continue;

                        if (parity[v] == -1) {
                            parity[v] = parity[u] ^ 1;
                            q.push(v);
                        }
                    }
                }
            }

            vector<int> ans(n + 1);

            for (int i = 1; i <= n; i++) {
                if (side[i] == 0) {
                    ans[i] = 1 + parity[i]; // 1 or 2
                } else {
                    ans[i] = 3 + parity[i]; // 3 or 4
                }
            }

            for (int i = 1; i <= n; i++) {
                if (i > 1) cout << ' ';
                cout << ans[i];
            }

            cout << '\n';
        }
    }

    return 0;
}