Depth First Search $($DFS$)$ is a fundamental graph traversal used as building block to solve important graph problems such as Topological Sort, finding Strongly Connected Components, and others. Hence, the time efficiency of those algorithms depends heavily on implementing efficiently DFS$.$

Given a directed graph $\backslash ($ G$=\backslash \{\backslash$mathrm$\{$V$\},\backslash$mathrm$\{$E$\}\backslash \}\backslash )$ encoded as an adjacency list, an efficient implementation of DFS runs in $\backslash (\backslash$mathrm$\{$O$\}(|\backslash$mathrm$\{$V$\}|+|$E$|)\backslash )$ steps.

The purpose of this homework is to evaluate experimentally the performance of an efficient implementation of DFS$.$

$1.(50$ points$)$ Write a program that, given the adjacency list of a directed graph, computes DFS efficiently. Your program should do the following.

$1.$ Prompt the user to input the number of nodes and the number of edges.

$2.$ Create an adjacency list choosing the edges at random $($do not forget that it is a directed graph$).$

$3.$ Compute DFS $($including discovery and finishing times$)$ following the pseudocode in the textbook $($attached$).$

$4.$ Measure and display the running time