Given an undirected graph G = (V, E), the square of it is the graph G2 = (V, E2 ) such that for any two nodes u, v ? V , {u, v} ? E2 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 E2 .)

1.) 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(?2n)-time, and prove the running time of your algorithm.

2.) Propose an algorithm that takes as an input a graph G in the adjacency matrix model and outputs G2 in o(n 3 )-time. Prove the correctness and running time of your algorithm. (Hint: We call it an adjacency matrix for a reason...)