QUESTION $8$

Consider a breadth$-$first graph search $($BFS$)$ on the graph below, where $S$ is the start and $G$ is the goal state.

Assume that ties are broken alphabetically $($so a partial plan $Sx$A would be expanded before $SxB$ and $SAZ$ would be expanded before $SBA).$ You may find it helpful to execute the search on scratch paper.

Please enter the final path returned by breadth$-$first graph search in the box below. Your answer should be a string with $S$ as your first character and $G$ as your last character. For auto grading, don't include arrows or spaces in your submission. For example, if you believe the path is $SxG,$ please enter $SxG$ in the boX.