MergingGraph

You are given a directed graph. The graph may contain loops, and multiple edges may exist between pairs of vertices. You can merge a pair of vertices into a single vertex. When a pair of vertices is merged, outgoing and incoming edges from both vertices become outgoing and incoming edges, respectively, of the resulting vertex. For example, consider a graph with four vertices {a, b, c, d} and three edges {a->b, c->b, c->d}. If we merge vertices b and c, the resulting graph will have three vertices {a, bc, d} and three edges {a->bc, bc->bc, bc->d}.

A graph is a cycle if its vertices can be ordered v₀, v₁, ..., v_n-1 (where n is the total number of vertices) such that the following two properties are satisfied:

• Every edge in the graph goes from v_i to v_(i+1)%n.
• For all i between 0 and n-1, inclusive, there exists at least one edge that goes from v_i to v_(i+1)%n.

You are given a String[] adj. The ith element of adj is a space delimited list of integers representing all the outgoing edges from vertex i. Each integer represents the target vertex of an outgoing edge. Return the minimal number of merge operations necessary to convert the given graph into a cycle. If a solution doesn't exist, return the number of vertices in the given graph instead.