<p>There are a total of <code>numCourses</code> courses you have to take, labeled from <code>0</code> to <code>numCourses - 1</code>. You are given an array <code>prerequisites</code> where <code>prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that you <strong>must</strong> take course <code>a<sub>i</sub></code> first if you want to take course <code>b<sub>i</sub></code>.</p>

<ul>
	<li>For example, the pair <code>[0, 1]</code> indicates that you have to take course <code>0</code> before you can take course <code>1</code>.</li>
</ul>

<p>Prerequisites can also be <strong>indirect</strong>. If course <code>a</code> is a prerequisite of course <code>b</code>, and course <code>b</code> is a prerequisite of course <code>c</code>, then course <code>a</code> is a prerequisite of course <code>c</code>.</p>

<p>You are also given an array <code>queries</code> where <code>queries[j] = [u<sub>j</sub>, v<sub>j</sub>]</code>. For the <code>j<sup>th</sup></code> query, you should answer whether course <code>u<sub>j</sub></code> is a prerequisite of course <code>v<sub>j</sub></code> or not.</p>

<p>Return <i>a boolean array </i><code>answer</code><i>, where </i><code>answer[j]</code><i> is the answer to the </i><code>j<sup>th</sup></code><i> query.</i></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/01/courses4-1-graph.jpg" style="width: 222px; height: 62px;" />
<pre>
<strong>Input:</strong> numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
<strong>Output:</strong> [false,true]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/01/courses4-3-graph.jpg" style="width: 222px; height: 222px;" />
<pre>
<strong>Input:</strong> numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
<strong>Output:</strong> [true,true]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= numCourses &lt;= 100</code></li>
	<li><code>0 &lt;= prerequisites.length &lt;= (numCourses * (numCourses - 1) / 2)</code></li>
	<li><code>prerequisites[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= numCourses - 1</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>All the pairs <code>[a<sub>i</sub>, b<sub>i</sub>]</code> are <strong>unique</strong>.</li>
	<li>The prerequisites graph has no cycles.</li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= numCourses - 1</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
</ul>

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        adj = {i:[] for i in range(numCourses)}
        res = []

        for a,b in prerequisites:
            adj[a].append(b)
        
        def dfs(a,b,visit):
            if a in visit:
                return False
            if a == b:
                return True
            visit.add(a)
            for nei in adj[a]:
            #     if not dfs(nei,b,visit):
            #         return False
            # return True
                if dfs(nei,b,visit):
                    return True # we do this instead of the above because if any of the path worked, we return True; our focus is not detecting a cycle and if so return False but if we detect any path containing target, we return True; this prevents us to prematurely returning False for nodes that do not directly lead to the target node, even though a valid path might exist through another branch of the search.
            return False
            
        return [True if dfs(a,b,set()) else False for a,b in queries]

# from collections import defaultdict, deque

# class Solution:
#     def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
#         neighbors = {node: set() for node in range(numCourses)}    # store the graph
#         indegree = defaultdict(int)     # store indegree info for each node
#         pre_lookup = defaultdict(set)   # store the prerequisites info for each node
        
#         # create the graph
#         for pre, post in prerequisites:
#             neighbors[pre].add(post)
#             indegree[post] += 1
        
#         # add 0 degree nodes into queue for topological sort
#         queue = deque([])
#         for n in neighbors:
#             if indegree[n] == 0:
#                 queue.append(n)
        
#         # use BFS to do topological sort to create a prerequisite lookup dictionary
#         while queue:
#             cur = queue.popleft()
#             for neighbor in neighbors[cur]:
#                 pre_lookup[neighbor].add(cur)                   # add current node as the prerequisite of this neighbor node
#                 pre_lookup[neighbor].update(pre_lookup[cur])    # add all the preqs for current node to the neighbor node's preqs
                
#                 indegree[neighbor] -= 1         # regular topological search operations
#                 if indegree[neighbor] == 0:
#                     queue.append(neighbor)
        
#         # traverse the queries and return the results
#         result = [True if q[0] in pre_lookup[q[1]] else False for q in queries]
        
#         return result
19500