First, let's create our own $`$Frontier$\_$PQ$`$ class to represent the frontier $($priority queue$)$ for uniform$-$cost search. Note that the $`$heapq$`$ package is imported in the helpers at the bottom of this notebook; you may find that package useful. You could also use the $`$Queue$`$ package. Your implementation of the uniform$-$cost search frontier should adhere to these specifications:

$*$ Instantiation arguments:

$***$Frontier$\_$PQ$($start$,$ cost$)**$

$***$start$**$ is the initial state $($e$.$g$.,**$start$**=$'chi'$)$

$***$cost$**$ is the initial path cost $($what should it be for the initial state?$)$

$*$ Instantiation attributes$/$methods:

$***$states$**$: maintains a dictionary of states on the frontier, along with the $\_$minimum$\_$ path cost to arrive at them

$***$q$**$: a list of $($cost$,$ state$)$ tuples, representing the elements on the frontier; should be treated as a priority queue $($in contrast to the $**$states$**$ dictionary, which is meant to keep track of the lowest$-$cost to each state$)$

$*$ appropriately initialize the starting state and cost

$*$ Methods to implement:

$***$add$($state$,$ cost$)**$: add the $($cost$,$ state$)$ tuple to the frontier

$***$pop$()**$: return the lowest$-$cost $($cost$,$ state$)$ tuple, and pop it off the frontier

$***$replace$($state$,$ cost$)**$: if you find a lower$-$cost path to a state that's already on the frontier, it should be replaced using this method.