(b) Consider two vertices x and y that are simultaneously on the function-call stack at some point during the execution of depth-first search from vertex s in a digraph. (That is, dfs(x) is called during the execution of dfs (y), or vice versa. In addition, the initial call is dfs(s).) Which of the following must be true? For each sub-problem, indicate your answer by circling the appro- priate response. I. There is both a directed path from s to x and a directed path from s to y. Must be true May be false II. If there is not a directed path from x to y, then there must be a directed path from y to x. Must be true May be false III. There is both a directed path from x to y and a directed path from y to x. Must be true May be false

(b) Consider two vertices x and y that are simultaneously on the function-call stack at some point during the execution of depth-first search from vertex s in a digraph. (That is, dfs(x) is called during the execution of dfs (y), or vice versa. In addition, the initial call is dfs(s).) Which of the following must be true? For each sub-problem, indicate your answer by circling the appro- priate response. I. There is both a directed path from s to x and a directed path from s to y. Must be true May be false II. If there is not a directed path from x to y, then there must be a directed path from y to x. Must be true May be false III. There is both a directed path from x to y and a directed path from y to x. Must be true May be false