Explore an HTTP Maze

You are given an HTTP API that represents a maze-like forest. The entrance is available at GET /mirkwood.

Each location in the forest is identified by a string id. A GET request to a location returns JSON describing that location and the possible next moves. Your program must explore the forest until it reaches the exit, then print the final location id.

Assume the API follows this contract:

{
  "id": "A",
  "message": "optional text",
  "neighbors": [
    { "direction": "north", "url": "/mirkwood?location=B" },
    { "direction": "east", "url": "/mirkwood?location=C" }
  ]
}

The exit response contains:

{
  "id": "Z",
  "message": "DONE",
  "neighbors": []
}

Requirements:

1. Write a program that repeatedly sends GET requests, explores reachable locations, and stops when it receives a response whose message is exactly "DONE".
2. Because the forest becomes more dangerous the farther you go, explore shallower locations before deeper ones. In other words, find the exit using breadth-first search.
3. Avoid infinite loops if the maze contains cycles.
4. Print the id of the final exit location.
5. Log enough information while exploring to debug unexpected API responses.

Follow-up:

A second endpoint uses the same maze idea but adds real-world API complications:

• Some requests may fail temporarily with server errors such as HTTP 500, 502, or 503.
• Some doors are locked. A neighbor may contain "locked": true and "required_key": "red".
• Some locations contain keys, for example "keys": ["red", "blue"].
• A locked door can only be traversed after your program has collected the required key.

Extend your program so it can still escape the maze while handling retries for transient failures, collecting keys, and revisiting locations when newly collected keys make additional paths available.