Question $3(40)$ : $($Searches and Search Trees$)$ This problem concerns an undirected graph $U$ and a directed graph $D,$ each of which has nine nodes. The graph $U$ has twelve undirected edges, and $D$ has twelve directed edges in each direction, for a total of $24$ directed edges.

The graphs concern nine towns $($in MA$,$ CT$,$ and NY$)$ with travel permitted either by car or bike between adjacent towns in the graph.

We first have the undirected graph $U$ for driving times by car:

$(a,10)$ Carry out a DFS search for the undirected graph $U,$ beginning with node EGR and with no goal node. List the order in which the nodes are placed on the open list $($call this the $"$On Order"$).$ If a node is placed on the list multiple times, it should be listed each time. Separately list the order in which each node is taken off the open list $($call this the "Out Order"$).$

When two or more nodes need to come off the list, and they entered at the same time, take the one first that comes earlier alphabetically.

Also draw the DFS tree, indicating the tree edges and the back edges.