Let G = (V, E) be a directed graph with nodes v1, v2, . . . vn. We say that G is an ordered graph if it has the following properties. (i) Each edge goes from a node with a lower index to a node with a higher index. That is, every directed edge has the form (vi , vj ) with i < j. (ii) Each node except vn has at least one edge leaving it. That is, for every node vi , i = 1, 2, . . . , n ? 1, there is at least one edge of the form (vi , vj ). The length of a path is the number of edges in the path.

Given an ordered graph G, find the length of the longest path that begins at v1 and ends at vn. Use a dynamic programming approach. What is the time complexity of your solution?