1103. Course Schedule IV — Reachability Queries

There are n courses labeled 0..n-1 with prerequisite edges [a, b] meaning a is a prerequisite of b. For each query [u, v], determine whether u is a (direct or indirect) prerequisite of v. Return the boolean answers as an array in order. The input is JSON {n, edges, queries}.

Input: JSON {n, edges, queries}.

Output: Array — a boolean per query.

Examples

Input: {"n":3,"edges":[[0,1],[1,2]],"queries":[[0,2],[2,0]]}
Output: [true,false]
Explanation: 0 reaches 2 but not vice versa.

Input: {"n":2,"edges":[],"queries":[[0,1],[1,0]]}
Output: [false,false]
Explanation: No prerequisites.

Input: {"n":4,"edges":[[0,1],[0,2],[1,3]],"queries":[[0,3],[3,0],[1,2]]}
Output: [true,false,false]
Explanation: Transitive reachability.

Constraints

• 2<=n<=100

Asked by