Problem 3. Counting Paths (22 points) Let G be a directed acyclic graph with n vertices, and let s, t be two labeled vertices in G. (a) (6 points) Argue that there can be as many as 2n-2 directed paths from s to t (b) (16 points) Give an O(n+m) time algorithm to count the number of directed paths which start at s and end at t, in any directed acyclic graph with n vertices and m edges. In addition to a clear description of the algorithm, make sure to include explanations for correctness and running time. Problem 3. Counting Paths (22 points) Let G be a directed acyclic graph with n vertices, and let s, t be two labeled vertices in G. (a) (6 points) Argue that there can be as many as 2n-2 directed paths from s to t (b) (16 points) Give an O(n+m) time algorithm to count the number of directed paths which start at s and end at t, in any directed acyclic graph with n vertices and m edges. In addition to a clear description of the algorithm, make sure to include explanations for correctness and running time