A degree programme has n modules numbered 0 .. n-1. The list prereqs contains pairs [a, b] meaning module a must be passed before module b. The prerequisite graph is guaranteed to be acyclic. Module a is an indirect prerequisite of b if there is a chain a -> ... -> b of one or more prerequisite pairs.
Given a list queries of pairs [u, v], return a list of booleans where the i-th entry is True exactly when u is a direct or indirect prerequisite of v.
Examples
Input: n = 4, prereqs = [[0, 1], [1, 2], [3, 2]], queries = [[0, 2], [2, 0], [3, 1], [0, 0]]
Output: [True, False, False, False]
Explanation: 0 -> 1 -> 2 exists; nothing leads into 0; 3 and 1 are unrelated; a module is not its own prerequisite.
Input: n = 2, prereqs = [], queries = [[0, 1]]
Output: [False]
Constraints
1 <= n <= 1000,0 <= len(prereqs) <= 5000,0 <= len(queries) <= 10**4- Target: O(n * (n + E) / 64 + Q) time using bitsets, or O(n * (n + E) + Q).
Goals
- Precompute transitive reachability once and answer many queries in O(1)
- Use Python integers as bitsets to keep the propagation fast