You will be given a Directed Graph of N nodes (numbered 0 to N-1) and a dummy node X .
Each of the N nodes will have ONE outgoing edge to any of the other nodes or to X .
A path is Valid if it is edge disjoint , begins on the node ‘0’ and ends on the dummy node X .
You are allowed to change AT MOST one edge in the Directed Graph i.e take any node u in [0,N-1] and replace the existing edge (u->v) with an edge (u->x) where x can be any node of your choice (including dummy node!).
You have to maximise the length of the Longest Valid Path in the Resulting Graph.
Note: The graph may have self loops/cycles. An edge disjoint path is one in which no edges are repeated.
The first line of input has the number of Nodes N
The second line of input comprises N space separated Integers.
The ith no ‘y’ in second line denotes a directed edge between (i-1) and y . Dummy Node X is represented as -1
-1 -1 -1 -1
Ans = 2 ( Replace Node ‘0’s edge by adding edge from ‘0’ to any other node from [1,3] )
1 2 3 -1
Ans = 4 ( The Initial Graph is Optimal )