Consider the following Constrained Reachability problem: the input consists of a directed graph G(V, E), two vertices s, t V , and a subset U V , where U {s, t} = . The output is yes if and only if there is a path from s to t in the graph without using any vertex in U. Apparently, the problem is the commonly known Reachability problem when U = . (1)

Design a recursive DFS type of algorithm to Constrained Reachability solve problem. You may assume that the input graph is already stored in adjacency lists and v. indicates if vertex v is in the set U or not. The information about is also given along with the graph.

(2) Argue that your algorithm still runs in linear time (i.e., O(|E| + |V |)-time) though the set U may contain a large number of vertices.