Please write clearly and concisely, and use rigorous, formal arguments. If you are asked to provide an algorithm the best thing to do is to provide a clear description in English (for example: "Use BFS, but with the following small change...", or "Run BFS two times as follows..."), but you may also write some short pseudocode similar to the pseudocode in the DPV text. (3) You are given two connected undirected graphs, G = (, E1) and G2 = (,), with Vin = 0, as well as a node s Vi and a node t . You are also given a set of edges E, which you are able to build: each edge in E, has one endpoint in Vi and one endpoint in . Thus, building any edge of E' would connect the two graphs together, and in particular would form paths connecting s and t. You are asked to determine an edge e E' whose addition to the graphs G1 and G2 would result in the shortest possible (i.e., smallest number of edges) distance between s and t among all the edges in E'Give a linear-time algorithm to solve this problem. Just give the algorithm, no proofs are necessary. Recall that "linear-time" means linear in the size of the input, which for this case is the number of nodes plus the number of edges in the graphs Gi and G2, plus the number of edges in E'. Hint: you can use BFS as a subroutine to solve this