(20 points) Given an undirected graph G = (V. E), the square of it is the graph G2-(VE2) such that for any two nodes u, u , {u'r) E E2 if and only if the distance between u and u in G is at most 2, i.e.,u,vEE or there is a wEV such that (u, w. sw, v) E. (Therefore, it is clear that any e E E will remain an edge also in E2.) (a) (10 points) Propose an algorithm that takes as an input a graph G with a max-degree of in the adjacency list model and outputs G2 in O(A2n)-time, and prove the running time of your algorithm. (b) (10 points) Propose an algorithm that takes as an input a graph G in the adjacency matriaz model and outputs G2 in o(n3)-time. Prove the correctness and running time of your algorithm