#include<bits/stdc++.h>

#ifdef THEMIS
#include "testlib_themis.h"
const std::string TASK_NAME = "STARNET";
#else
#include "testlib.h"
#endif // THEMIS

using namespace std;

// Cấu trúc Disjoint Set Union (DSU) để kiểm tra tính liên thông và chu trình
struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }
    bool 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;
            return true;
        }
        return false;
    }
};

void check() {
    // Đọc n và m từ file input
    int n = inf.readInt();
    int m = inf.readInt();

    // Lưu trữ các cạnh của đồ thị gốc để kiểm tra tính hợp lệ
    // Sử dụng set để tra cứu nhanh O(log m)
    set<pair<int, int>> original_edges;
    vector<int> original_deg(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        int u = inf.readInt();
        int v = inf.readInt();
        if (u > v) swap(u, v);
        original_edges.insert({u, v});
        original_deg[u]++;
        original_deg[v]++;
    }

    // Tính bậc lớn nhất có thể đạt được.
    // Trong bài toán này, bậc lớn nhất của cây khung tối ưu luôn bằng bậc lớn nhất của đồ thị gốc.
    int max_deg_possible = 0;
    for (int i = 1; i <= n; ++i) {
        max_deg_possible = max(max_deg_possible, original_deg[i]);
    }

    // Chuẩn bị cấu trúc để kiểm tra output của thí sinh
    DSU dsu(n);
    vector<int> user_deg(n + 1, 0);

    // Đọc n - 1 cạnh từ output của thí sinh
    for (int i = 0; i < n - 1; ++i) {
        int u = ouf.readInt(1, n, "u");
        int v = ouf.readInt(1, n, "v");

        if (u == v) {
            quitf(_wa, "Canh cua cay khung khong duoc la khuyen: %d %d", u, v);
        }

        if (u > v) swap(u, v);

        // 1. Kiểm tra cạnh có tồn tại trong dữ liệu đầu vào không
        if (original_edges.find({u, v}) == original_edges.end()) {
            quitf(_wa, "Canh %d-%d khong ton tai trong do thi ban dau", u, v);
        }

        // 2. Kiểm tra chu trình (nếu 2 đỉnh đã thuộc cùng một thành phần liên thông thì thêm cạnh sẽ tạo chu trình)
        if (!dsu.unite(u, v)) {
            quitf(_wa, "Cac canh in ra tao thanh chu trinh hoac bi trung lap tai canh %d-%d", u, v);
        }

        // Cập nhật bậc của đỉnh trong cây khung của thí sinh
        user_deg[u]++;
        user_deg[v]++;
    }

    // Kiểm tra xem output còn dữ liệu thừa không
    if (!ouf.seekEof()) {
        quitf(_wa, "Output chua nhieu hon n-1 canh hoac co du lieu thua");
    }

    // Vì chúng ta đã đọc đúng n-1 cạnh và đảm bảo không có chu trình trên n đỉnh,
    // nên chắc chắn các cạnh này tạo thành một cây khung (liên thông).

    // 3. Kiểm tra điều kiện tối ưu (Bậc lớn nhất)
    int user_max_deg = 0;
    for (int i = 1; i <= n; ++i) {
        user_max_deg = max(user_max_deg, user_deg[i]);
    }

    if (user_max_deg == max_deg_possible) {
        quitf(_ok, "Chinh xac! Bac lon nhat la %d", user_max_deg);
    } else {
        quitf(_wa, "Ket qua chua toi uu. Bac lon nhat du kien %d, tim thay %d", max_deg_possible, user_max_deg);
    }
}

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