Same Shape Trees

Two rooted trees are given as parent lists: first[i] is the parent of node i in the first tree, and the root's entry is -1. second describes the second tree in the same way. The node numbers carry no meaning, and neither does the order of a node's children.

Two trees have the same shape when one can be drawn from the other by renumbering its nodes and reordering the children of any node. In other words, the two roots have the same number of children, and those children can be paired up so that each pair again has the same shape, all the way down. Write same_shape(first, second) that returns True if the trees have the same shape and False otherwise.

Examples

same_shape([-1, 0, 0, 1], [-1, 0, 0, 2])  # returns True
same_shape([-1, 0, 0, 1, 1], [-1, 0, 0, 1, 2])  # returns False
same_shape([2, 2, -1, 0], [-1, 0, 1, 0])  # returns True

In the second example both trees have a root, two nodes below it and two more below those. But in the first tree both lower nodes hang from the same parent, while in the second they hang from different parents. In the third, the first tree's root is node 2.

Constraints

• Each tree has 1 to 30,000 nodes, and each list has exactly one -1.

Note

• A tree can be a single chain of 30,000 nodes. Python stops recursion at about 1,000 levels, so a recursive search has to be rewritten with a stack of your own.