Question 3 (2 points): Recall the DFS algorithm for directed graphs. Suppose that we define two labels for each node, Du stores the first visit by DFS to node u discovery time), and Nu stores the last visit by DFS at node u finish time). That is, we compute the labels using the following algorithm: DFS-algorithm computing labels D and N 2:=0; // global variable : V EV: D[u] := N [y] := 0; // initialise the arrays while 3v e V with N[u] = 0 do DFS(G,U); DFS( G1) visit r; D[v] := ++2; forall (x,y) E E do if y is unvisited then DFS(G,y); T:=TU{x,y)}; // T is a global variable defining DFS tree od NU: ++2; Prove that if we run the DFS algorithm above to compute all values D and N, then for any pair of vertices uv EV, the values D and N satisfy the following two properties: 1. u is an ancestor of v in the DFS-forest if and only if the interval [D[u], [w]] is contained in the interval [D[u], N[u]] (that is, [D[u], [u] S [D[u]N[u]]); 2. u and v are unrelated in the DFS-forest if and only if the intervals [D[u]N[Mand [D[], N[v]] are disjoint (that is, [D[u], [u]] [D[0], N [0]] = 0)