OI XXXII - bit (Alt)

// https://szkopul.edu.pl/problemset/problem/wOKsnzwNqHqXqiX6m3AkufgX/site/?key=statement

// Bitada

#include <bits/stdc++.h>

constexpr int sizik = 3005;

int n, m;
int64_t M;

struct T1Edge {
    int u, v;
    int id;
    int next_count;
    int next_ids[3];
};

std::vector<T1Edge> t1_edges;
std::vector<int> t1_node_outgoing[sizik];

std::vector<int> adj2[sizik];
std::vector<int> children2[sizik];
std::vector<int> post_order;

int64_t dp[sizik][2 * sizik];

void build_t2_structure(int u, int p) {
    for (int v : adj2[u]) {
        if (v != p) {
            children2[u].push_back(v);
            build_t2_structure(v, u);
        }
    }
    post_order.push_back(u);
}

inline int64_t match(const int* t1_out_ids, int t1_count, const std::vector<int>& t2_kids) {
    int k = t1_count;
    int l = t2_kids.size();

    if (k > l) return 0;
    if (k == 0) return 1;

    int64_t res = 0;

    if (k == 1) {
        int e1 = t1_out_ids[0];
        for (int i = 0; i < l; ++i) {
            res += dp[t2_kids[i]][e1];
        }
    } else if (k == 2) {
        int e1 = t1_out_ids[0];
        int e2 = t1_out_ids[1];
        for (int i = 0; i < l; ++i) {
            for (int j = 0; j < l; ++j) {
                if (i == j) continue;
                int64_t val = (dp[t2_kids[i]][e1] * dp[t2_kids[j]][e2]) % M;
                res += val;
            }
        }
    } else if (k == 3) {
        int e1 = t1_out_ids[0];
        int e2 = t1_out_ids[1];
        int e3 = t1_out_ids[2];
        for (int i = 0; i < l; ++i) {
            for (int j = 0; j < l; ++j) {
                if (i == j) continue;
                for (int z = 0; z < l; ++z) {
                    if (z == i || z == j) continue;
                    int64_t val = (dp[t2_kids[i]][e1] * dp[t2_kids[j]][e2]) % M;
                    val = (val * dp[t2_kids[z]][e3]) % M;
                    res += val;
                }
            }
        }
    }

    return res % M;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> n >> m >> M;

    if (n == 1) {
        std::cout << m % M << "\n";
        return 0;
    }

    std::vector<std::pair<int, int>> temp_edges;
    std::vector<std::vector<int>> raw_adj1(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        raw_adj1[u].push_back(v);
        raw_adj1[v].push_back(u);
        temp_edges.push_back({u, v});
    }

    for (int u = 1; u <= n; ++u) {
        for (int v : raw_adj1[u]) {
            T1Edge e;
            e.u = u;
            e.v = v;
            e.id = t1_edges.size();
            e.next_count = 0;
            t1_edges.push_back(e);

            t1_node_outgoing[u].push_back(e.id);
        }
    }

    std::vector<int> out_ids_per_node[sizik];
    for (const auto& e : t1_edges) {
        out_ids_per_node[e.u].push_back(e.id);
    }

    for (auto& e : t1_edges) {
        for (int candidate_id : out_ids_per_node[e.v]) {
            if (t1_edges[candidate_id].v != e.u) {
                e.next_ids[e.next_count++] = candidate_id;
            }
        }
    }

    int root_t2 = 1;
    std::vector<int> deg2(m + 1, 0);
    for (int i = 0; i < m - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj2[u].push_back(v);
        adj2[v].push_back(u);
        deg2[u]++;
        deg2[v]++;
    }

    if (m > 1) {
        for (int i = 1; i <= m; ++i) {
            if (deg2[i] == 1) {
                root_t2 = i;
                break;
            }
        }
    }
    build_t2_structure(root_t2, 0);

    for (const auto& v : post_order) {
        const auto& v_children = children2[v];

        for (const auto& t1_e : t1_edges) {
            dp[v][t1_e.id] = match(t1_e.next_ids, t1_e.next_count, v_children);
        }
    }

    int64_t total_ans = 0;

    for (int v = 1; v <= m; ++v) {
        for (int u = 1; u <= n; ++u) {
            int tmp_ids[3];
            int cnt = 0;
            for (int id : t1_node_outgoing[u])
                tmp_ids[cnt++] = id;

            total_ans = (total_ans + match(tmp_ids, cnt, children2[v])) % M;
        }
    }

    std::cout << total_ans << "\n";

    return 0;
}