Let G = (V, E) be an undirected graph on the nodes V = {1, . . . , n}. Suppose the edges of the graph are removed one by one in some order e1, . . . , em. After the removal of some edge ei the graph will have no cycles remaining. Assume the e1, . . . , em edges are given as an array A[1 . . m], where A[i] contains the tuple of vertices ei = (u, v). Give an algorithm that, when given as input n and the array A, outputs the smallest positive integer i such that the graph Gi = (V, E {e1, . . . , ei1}) has no cycles. (Define G1 = G.) The running time of your algorithm must be asymptotically better than O(mn). Give pseudocode for your algorithm, analyze its running time, and prove it is correct

Question 2. (1 marks) Let G- (V, E) be an undirected graph on the nodes V -1,...,n). Suppose the edges of the graph are removed one by one in some order e1,..., em- After the removal of some edge ej the graph will have no cycles remaining. Assume the e1,... , em edges are given as an array A[1..m where Ale] contains the tuple of vertices e (u, v). Give an algorithm that, when given as input n and the array A, outputs the smallest positive integer i such that the graph Gi (V,E e1,.. , ei-1]) has no cycles. (Define Gi - G.) The running time of your algorithm must be asymptotically better than O(mn). Give pseudocode for your algorithm, analyze its running time, and prove it is correct