3) (16 pts.) (i) G is an undirected graph on n vertices and m edges. Given two vertices u and v, you need to determine whether G contains three cycles of length three, each including the edge (u, v). For example, graph G1 in the figure below contains 4 triangles, but not three triangles that contain a common edge. Describe and analyze an efficient algorithm when (a) G is represented by adjacency lists (give the time bound in terms of n and m) and (b) G is represented by an adjacency matrix (give the time bound in terms of n) (ii) G is an undirected graph on n vertices and m edges represented by adjacency lists. Describe and analyze and O(n m) time algorithm determining whether G contains exactly two cycles of length at least three that are edge-disjoint. Edge disjoint means any edge of G can only appear in at most one cycle. For example, graph G2 in the figure below contains two edge disjoint cycles. 0 4 Graph G1 Graph G2 (iii) A game consists of n levels, numbered from 1 to n. To win the game, one needs to play all n levels. Some levels have conditions on what levels need to be played before. These conditions are given in the form of pairs [p, q indicating level p is required for level q. For example, if the pair [4,2 is present, level 4 needs to be played before level 2. For n- 4 and the pairs [1,3 and [3,2], the levels can be payed in the order 1,3,4,2 Given n and m pairs, describe and analyze an efficient algorithm determining an order in which to play the n levels so that the orderings given by the pairs is satisfied. If no order exists, determine so. If multiple solutions exist, choose an arbitrary one. Express any bounds in terms of n and m