1. For an acyclic network G with a specified source node s, outline an algorithm that enumerates all distinct directed paths from the source node to every other node in the network. The running time of your algorithm should be proportional to the total length of all the paths enumerated (i.e., linear in terms of the output length.)

2. In an undirected connected graph G = (N, A), an Euler tour is a walk that starts at some node, visits each arc exactly once, and returns to the starting node. A graph is Eulerian if it contains an Euler tour. Show that in an Eulerian graph, the degree of every node is even. Next, show that if every node in a connected graph has an even degree, the graph is Eulerian. Establish the second result by describing an O(m) algorithm for determining whether a graph is Eulerian and, if so, will construct an Euler tour. (Hint: Describe an algorithm that decomposes any graph with only even-degree nodes into a collection of arc-disjoint cycles, and then converts the cycles into an Euler tour.)