Nested Dictionary Value Retrieval

You are given a JSON object representing a nested dictionary and a target key. Your task is to traverse the dictionary using a breadth-first search (BFS) and retrieve the value associated with the given key. If the key is present in multiple levels, return the value from the shallowest occurrence. If the key is not found, output 'Key not found'.

The BFS algorithm used here has a time complexity of (O(n)), where (n) is the number of elements in the dictionary.

inputFormat

The input consists of two lines. The first line contains a JSON string representing a nested dictionary. The second line contains the target key as a string.

outputFormat

Print the value associated with the target key to stdout. If the key is not found in the dictionary, print 'Key not found'.## sample

{"name": "Alice", "details": {"age": 30, "location": {"city": "Wonderland", "zipcode": "12345"}}}
name

Alice