A tree is to be constructed as in question 2. Compute the minimum depth of the tree. Minimum Depth is defined as the number of nodes in the shortest path from root to leaf. A node with only a root node is assumed to have a depth of 1.

Input format and constraints are same as question .

Output Format:

Print a single integer denoting the minimum depth of the tree.