Use A$*$ search with an Extended List to find both the path and the extended node list. Use this space to drawthe corresponding tree and show your work. Mark each node as you extend it by putting a number in a circlenext to the node corresponding to when it was extended.Assume that the line$-$of$-$ sight distances providedare admissible heuristics for the distances to the goal.Search Tree:$1$S$2$B$2+2=43$C$3+4=74$D$3+5=85$F$4+5=9$C$5+4=9$D$5+5=10$BD$7+5=12$F$6+5=11$BCA$7+5=12$C$6$E$7+3=10$A$10+5=157$G$10+0=10$Node extension order is given in circles at the top$-$left of the corresponding node. Estimated cost ofeach path is written in red at the bottom of the corresponding node. Nodes that have already beenextended are filled with gray.Path:SFEGExtended Nodes in order Extended:SBCDFEGPage $5$