Consider navigating the maze shown below.

The maze is represented as a graph with edge costs as shown on the edges. The edge cost is 1 for all edges where the cost is not shown. Let S be the initial state and G is the goal state. The heuristic cost of every node to reach G is :

h	h(n)
A	5.1
B	4.1
C	3.9
D	4
E	2.2
F	3.8
G	0
H	3.7
J	7
K	6
L	4
M	0.5
N	1.5
P	1.8
S	4.5

List the vertices expanded by a A* search (enter the single letter label of a node).

1. S

2. B

3. ?

4. ?

5.?

6.?

7.?

8.?

Please answer number 3-8

Note:

A node is "expanded" when it is taken out of the frontier and its children are inserted

Child states of a state are generated in alphabetical order