1- Consider the following statement: If a directed graph G = (V,E) is acyclic and no edge between u and v is in E, then at least one of (u,v) or (v,u) can be added to E without creating a cycle. Give a (short) proof that this statement is correct or find a counterexample.

2- Show how to modify Dijkstra's algorithm to count the number of minimum costs paths from the source vertex s to all other vertices.