(25 Points) Give a linear time (O(V|+E)) algorithm that takes as input a DAG (directed acyclic graph) in adjacency list format and two vertices s and t, and returns the number of directed paths from s to t. Prove that your algorithm is correct and argue its time complexity. Note: Two paths that overlap are counted as two distinct paths. For example, there are three distinct paths in the below graph: {s, a, d, t}, {s, b, d, t} and {s, c, d, t}, even though they have (d, t) in common