#ifdef THEMIS
#include "testlib_themis.h"
// Tên bài phải khớp với tên file input/output
const std::string TASK_NAME = "ROADS"; 
#define _100 1.0
#else
#include "testlib.h"
#define _100 100.0
#endif // THEMIS

#include <vector>
#include <string>
#include <numeric>

// Một cấu trúc Disjoint Set Union (DSU) đơn giản để quản lý các thành phần liên thông
struct DSU {
    std::vector<int> parent;
    int components;
    DSU(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0);
        components = n;
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
        }
    }
};


int main(int argc, char* argv[]) {
#ifdef THEMIS
    registerTestlibThemis(TASK_NAME + ".inp", TASK_NAME + ".out");
#else
    registerTestlibCmd(argc, argv);
#endif

    // 1. Đọc file input và xây dựng đồ thị ban đầu bằng DSU
    int n = inf.readInt(1, 100000, "n");
    int m = inf.readInt(0, 200000, "m");
    
    DSU dsu(n);

    for (int i = 0; i < m; ++i) {
        int u = inf.readInt(1, n, "u");
        int v = inf.readInt(1, n, "v");
        dsu.unite(u, v);
    }

    // 2. Tính toán kết quả đúng từ đồ thị ban đầu
    // Số đường cần xây = (số thành phần liên thông) - 1
    int jury_k = dsu.components - 1;

    // 3. Đọc và kiểm tra output của thí sinh
    int cont_k = ouf.readInt(0, n - 1, "k");

    // 4. So sánh số lượng đường cần xây
    if (cont_k != jury_k) {
        quitf(_wa, "Incorrect number of roads to build. Expected %d, found %d", jury_k, cont_k);
    }

    // Nếu k=0, không cần đọc thêm, đồ thị đã liên thông.
    if (cont_k == 0) {
        quitf(_ok, "Correct. The graph is already connected.");
    }
    
    // 5. Đọc các đường đi thí sinh đề xuất và kiểm tra xem chúng có thực sự kết nối đồ thị không
    for (int i = 0; i < cont_k; ++i) {
        int u = ouf.readInt(1, n, "u");
        int v = ouf.readInt(1, n, "v");
        dsu.unite(u, v);
    }
    
    // 6. Kiểm tra lại số thành phần liên thông sau khi thêm đường
    if (dsu.components == 1) {
        quitf(_ok, "Correct. %d roads built and the graph is connected.", cont_k);
    } else {
        quitf(_wa, "The proposed roads do not connect all cities. %d components remain.", dsu.components);
    }

    return 0;
}