int dfs(int node, vector<int>& A, vector<vector<int>>& adj, vector<int>& visited, int goodCount, int C) {
    visited[node] = 1;
    int count = 0;
    if (adj[node].size() == 0) {
        if (goodCount <= C) {
            return 1;
        }
        return 0;
    }
    if(goodCount>C) return 0;
    for (auto n : adj[node]) {
        if (visited[n] == 0) {
            if (A[n] == 1) {
                count += dfs(n, A, adj, visited, goodCount + 1, C);
            }
            if (A[n] == 0) {
                count += dfs(n, A, adj, visited, goodCount, C);
            }
        }
    }
    visited[node]=0;
    return count;
}

int Solution::solve(vector<int>& A, vector<vector<int>>& B, int C) {
    vector<vector<int>> adj(A.size() + 1);
    vector<int> visited(A.size() + 1, 0);
    for (auto edge : B) {
        adj[edge[0]].push_back(edge[1]);
        //adj[edge[1]].push_back(edge[0]);
    }
    return dfs(1, A, adj, visited, 0, C);
}