There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.


	For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.


Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.

Return a boolean array answer, where answer[j] is the answer to the jth query.

&nbsp;
Example 1:

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.


Example 2:

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.


Example 3:

Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]


&nbsp;
Constraints:


	2 &lt;= numCourses &lt;= 100
	0 &lt;= prerequisites.length &lt;= (numCourses * (numCourses - 1) / 2)
	prerequisites[i].length == 2
	0 &lt;= ai, bi &lt;= n - 1
	ai != bi
	All the pairs [ai, bi] are unique.
	The prerequisites graph has no cycles.
	1 &lt;= queries.length &lt;= 104
	0 &lt;= ui, vi &lt;= n - 1
	ui != vi


class Solution:
    """
    one approach I can think of is, given a graph, 
    the query[a, b] will be true if there exists a path from a to b in the graph
    else a will not be a prerequisite of b
    but this approach may not scale as the # of queries will increase
    """
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        graph = {node: set() for node in range(numCourses)}
        for pre in prerequisites:
            graph[pre[0]].add(pre[1])
        
        def path(cur_node, node_b):
            if cur_node == node_b:
                return True
            for neighbor in graph[cur_node]:
                if path(neighbor, node_b):
                    return True
            return False
            
        ans = []
        for query in queries:
            # see if there is a path from query[0] to query[1]
            ans.append(path(query[0], query[1]))
        return ans
class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        // Generating Map
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int e[]: prerequisites){
            graph.putIfAbsent(e[0], new ArrayList<>());
            graph.get(e[0]).add(e[1]);
        }

        List<Boolean> list = new ArrayList<>();
        // Appling DFS for every query to get result
        for(int[] q: queries){
            list.add(isPre(q[0], q[1], graph, new HashSet<>()));
        }
        return list;
    }
    // Check if src comes before dst using DFS
    private boolean isPre(int src, int dst, Map<Integer, List<Integer>> adj, Set<Integer> visited){
        if(visited.contains(src)) return false;
        visited.add(src);
        for(int neigh: adj.getOrDefault(src, new ArrayList<>())){
            if(neigh == dst || isPre(neigh, dst, adj, visited)) return true;
        }
        return false;
    }
}
// question similar to find all ancestors of current node

class Solution {

public:

    void dfs(vector<vector<int>>&adj,vector<set<int>>&Anc,int u,int par,vector<int>&vis)
    {
        if( vis[u] != 0 )
            return ;

        vis[u] = 1 ;

        for(auto&v:adj[u])
        {
            if( vis[v] == 0 )
            {
                Anc[v].insert(par) ;
                dfs(adj,Anc,v,par,vis) ;
            }
        }

        return ;
    }

    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {

        int n = numCourses ;
        vector<vector<int>>adj(n);
        vector<set<int>>Anc(n);
        vector<bool>ans;

        for(auto&edge:prerequisites)
        {
            adj[edge[0]].push_back(edge[1]) ;
        }

        for(int i=0;i<n;i++)
        {
            vector<int>vis(n,0);
            dfs(adj,Anc,i,i,vis) ;
        }

        for(auto&EachQuery:queries)
        {
            if( Anc[EachQuery[1]].find(EachQuery[0]) != Anc[EachQuery[1]].end() )
                ans.push_back(true);
            else
                ans.push_back(false) ;
        }
        return ans ;
    }

};
var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    let adj = {};
    for (let [from, to] of prerequisites) {
        if (!adj[from]) {
            adj[from] = [];
        }
        
        adj[from].push(to);
    }
    
    let set = {};
    Object.keys(adj).forEach(key => dfs(key));
    return queries.map(([a,b]) => set[a]?.has(b) || false);
    
    function dfs(cur) {
        if (set[cur]) {
            return set[cur];
        }
        
        if (!set[cur]) {
            set[cur] = new Set();
        }
        
        for (let n of (adj[cur] || [])) {
            set[cur].add(n);
            dfs(n);
            set[n].forEach(set[cur].add, set[cur]);
        }
    }
    
};
Course Schedule IV