1. Let G = (V,E) be a directed graph. Define a graph G2 = (V,E) as follows: V = V; u,vE ifthereisaapathoflength2betweenuandvinG.

Suppose that a directed graph G is given as adjacency list. Give a O(mn)-time algorithm to compute G2. Derive the time bound. Here m is number of edges in G and n is number of vertices in G.

Suppose that a directed graph G is given as adjacency matrix. Given an algorithm to compute G2. Derive the run time of your algorithm.