"""Implement these two contracts. Do not import the supplied reference to pass the tests.
A* graph: ordered dict of state -> [(destination, nonnegative cost), ...].
Heuristic: state -> nonnegative estimate, zero at goal. Reopen on cheaper paths.
Budget counts expanded non-goal states; goal selection at the cap is allowed.
Return status (found/budget/exhausted), route, cost (or None), expansions,
edgeReads and reopens. Never report a cutoff as exhaustive impossibility.

Filter: initial probabilities, from/to transition rows, per-observation likelihood rows.
A transition occurs before every observation; ones mean missing evidence.
Return status (complete/impossible), steps with predicted/evidence/posterior,
and logEvidence (None for impossible evidence). Do not invent a zero-weight posterior.
Keep input objects unchanged. Reference documentation states workload and input bounds.
"""


def astar(graph, heuristic, start, goal, budget=64):
    raise NotImplementedError('Implement a bounded priority search with reopening')


def filter_belief(initial, transition, likelihoods):
    raise NotImplementedError('Implement prediction, correction and zero-evidence stopping')