Deepest Level with At Least K Nodes

You are given an integer $K$ and a binary tree with $N$ nodes. The tree is provided as $N$ triples of integers in the following format:

where each triple represents a node. The first number in a triple is the node's identifier, and the second and third numbers are the identifiers of its left and right children respectively. A child identifier of -1 indicates that the child is missing. The first node given is always the root of the tree.

Your task is to determine the deepest level (0-indexed) in the tree such that there are at least $K$ nodes at that level. If no such level exists, output -1.

For example, consider the tree represented by the following list:

1 2 3 2 -1 -1 3 4 -1 4 -1 -1

For $K = 2$, level 0 has 1 node (node 1) and level 1 has 2 nodes (nodes 2 and 3), so the answer is 1.

Write a program that reads the input from standard input and writes the answer to standard output.

inputFormat

The first line contains two integers $K$ and $N$, where $K$ is the minimum number of nodes required and $N$ is the number of nodes in the tree. The next $N$ lines each contain three integers: $value$, $left$, and $right$. Here, $value$ is the identifier of a node, and $left$ and $right$ are the identifiers of its left and right children respectively, with -1 indicating a missing child. The first node given is the root of the binary tree.

outputFormat

Output a single integer representing the deepest level (0-indexed) that contains at least $K$ nodes. If no such level exists, output -1.## sample

2 4
1 2 3
2 -1 -1
3 4 -1
4 -1 -1

1