Problem 2. ( ShortestCommonAncestor Data Type) Implement an immutable data type ShortestCommonAncestor with the following API:

Corner cases. All methods and the constructor should throw a java.lang.NullPointerException if any argument is null . The constructor should throw a java.lang.IllegalArgumentException if the digraph is not a rooted DAG. The methods length() and ancestor() should throw a java.lang.IndexOutOfBoundsException if any argument vertex is invalid and an java.lang.IllegalArgumentException if any iterable argument contains zero vertices.

Performance requirements. Your data type should use space proportional to E + V , where E and V are the number of edges and vertices in the digraph, respectively. All methods and the constructor should take time proportional to E + V (or better). You will receive most of the credit for meeting these basic requirements. In addition, for full credit, the methods length() and ancestor() should take time proportional to the number of vertices and edges reachable from the argument vertices (or better), For example, to compute the shortest common ancestor of v and w in the digraph below, your algorithm can examine only the highlighted vertices and edges and it cannot initialize any vertex-indexed arrays.

And the result should look like this:

Here's the input file:

12 11 6 3 7 3 3 1 4 1 5 1 8 5 9 5 10 9 11 9 1 0 2 0

And here's the format should look like:

The only thing to do is just to change the " . . . " to real code. Thanks.

description construct a ShortestCommonAncestor object given a rooted DAG length of shortest ancestral path between v and w a shortest common ancestor of vertices v and uw length of shortest ancestral path of vertex subsets A and B shortest common ancestor of vertex subsets A and B method ShortestCommonAncestor (Digraph G) int length(int v, int w) int ancestor(int v, int w) int length(Iterable A, Iterable B) int ancestor (Iterable A, Iterable B)