In Star Wars Universe, there is a planet Naboo in which an AI agent named C$-3$PO diligently serves her Queen. Engaged in routine tasks, C$-3$PO unexpectedly comes into possession of crucial documents containing the secrets of the castle belonging to the Dark Lord, situated on the volcanic planet of Tectonica Magma. Upon discovering this, the Dark Lord swiftly dispatches his army to retrieve the documents from C$-3$PO$.$ Fearing the relentless pursuit of the Dark Lord$$s army, C$-3$PO seeks refuge within the shelter of a cave. Upon entering the cave, C$-3$PO discovers a map, realizing that it is currently located at grid position $0$ and must navigate through the cave to reach grid location $61$ in order to escape.

Dark Lord's army has got to know that C$-3$PO is hiding in the cave and set up the explosives in the cave that will go off after a certain time.

Let us use our knowledge of AI and help C$-3$PO to search his path out of the cave. C$-3$PO will follow the following rules for Searching the cave $($this logic is hardcoded in his memory$).$

$-$ The $($x$,$ y$)$ coordinates of each node are defined by the column and the row shown at the top and left of the maze, respectively. For example, node $13$ has $($x$,$ y$)$ coordinates $(1,5).$

$-$ Process neighbours in increasing order. For example, if processing the neighbours of node $13,$ first process $12,$ then $14,$ then $21.$

$-$ Use a priority queue for your frontier. Add tuples of $($priority$,$ node$)$ to the frontier. For example, when performing Uniform Cost Search and processing node $13,$ add $(15,12)$ to the frontier, then $(15,14),$ then $(15,21),$ where $15$ is the distance $($or cost$)$ to each node.

$-$ When removing nodes from the frontier $($or popping off the queue$),$ break ties by taking the node that comes first lexicographically. For example, if deciding between $(15,12),(15,14)$ and $(15,21)$ from above, choose $(15,12)$ first $($because

$-$ A node is considered visited when it is removed from the frontier $($or popped off the queue$).$

$-$ You can only move horizontally and vertically $($not diagonally$).$

$-$ It takes $1$ minute to explore a single node. The time to escape the maze will be the sum of all nodes explored, not just the length of the final path.

$-$ All edges have cost $1.$

You task is to answer the following questions, and provide pseudo codes and python source codes in support of your answers.

I$)$ If C$-3$PO uses a Uniform Cost Search, how many nodes will it explore and how long will it take C$-3$PO to escape the Cave?

II$)$ What if the Dark Lord also has the knowledge about the Uniform Cost Search, he updates the time of the explosive so that Uniform Cost Search will not work anymore for C$-3$PO$.$ What choice does C$-3$PO have now? Having studies Search Algorithms, C$-3$PO knows that A$*$ search works faster than Uniform cost search. He uses A$*$ search with the Manhattan distance heuristic. How much time will C$-3$PO take now to find the path out of the cave?

III$)$ C$-3$PO has received a valuable tip from a trusted AI agent friend, revealing that the Dark Lord has updated the timer. It is now apparent that a conventional A$*$ search may not suffice. Undeterred by the challenge, C$-3$PO$,$ leveraging his expertise, identifies a bottleneck in the maze. Specifically, the path between nodes $27$ and $35$ serves as the sole passage connecting the left and right halves of the maze. Recognizing this crucial point, C$-3$PO devises a strategy to split the search into two segments. Initially, he navigates from the starting point to the bottleneck $($node $27).$ Subsequently, he continues the search from the bottleneck $($node $35)$ to reach the final goal. The question now arises: how much time will it take for C$-3$PO to successfully exit the cave?