Given an undirected graph G = (V,E), the square of it is the graph G^2 = (V,E^2) such that for any two nodes u,v V , {u,v} E^2 if and only if the distance between u and v in G is at most 2, i.e., {u,v} E or there is a w V such that {u,w},{w,v} E. (Therefore, it is clear that any e E will remain an edge also in E^2.)

A) Propose an algorithm that takes as an input a graph G with a max-degree of in the adjacency list model and outputs G^2 in O((^2)n)-time, and prove the running time of your algorithm.

B) Propose an algorithm that takes as an input a graph G in the adjacency matrix model and outputs G^2 in o(n^3)-time. Prove the correctness and running time of your algorithm.