Hierarchy Depth and Ancestors

This problem involves processing a hierarchical structure of game objects. The hierarchy is represented as a JSON dictionary where each key is an object ID and its associated value is a list of child object IDs. The task is to compute two things for a given object:

• The depth in the hierarchy (with the root having a depth of 0).
• The list of ancestor object IDs from the root to the parent of the given object.

If the object does not exist in the hierarchy, output should be (None, []).

In mathematical terms, if we define d as the depth and A as the ancestor list then for the root node we have d = 0 and for any other node d = d_parent + 1.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. A JSON string representing the hierarchical dictionary. It maps each object ID (string) to a list of its children object IDs (list of strings).
2. A string representing the target object ID for which you need to find the depth and ancestors.

outputFormat

Output the result to standard output (stdout) as a tuple in the following format:

(depth, ["ancestor1", "ancestor2", ...])

If the object is not found in the hierarchy, output:

(None, [])

Note: The root’s depth is 0, and its ancestor list is empty.

## sample

{"root":["child1","child2","child3"],"child1":["subchild1","subchild2"],"child2":[],"child3":["subchild3"],"subchild1":[],"subchild2":[],"subchild3":["subsubchild1"],"subsubchild1":[]}
subchild2

(2, ["root", "child1"])