Monocarp was captivated by BFS such a lot of that, eventually, he lost his tree. Luckily, he actually has a grouping of vertices, wherein request vertices were visited by the BFS calculation (the cluster a from the pseudocode). Monocarp realizes that every vertex was visited precisely once (since they were put and taken from the line precisely once). Likewise, he realizes that all offspring of every vertex were
Correct answer will be upvoted else Multiple Downvoted. Don't submit random answer. Computer science.
Monocarp was captivated by BFS such a lot of that, eventually, he lost his tree. Luckily, he actually has a grouping of vertices, wherein request vertices were visited by the BFS calculation (the cluster a from the pseudocode). Monocarp realizes that every vertex was visited precisely once (since they were put and taken from the line precisely once). Likewise, he realizes that all offspring of every vertex were seen in rising request.
Monocarp realizes that there are many trees (in the overall case) with a similar visiting request a, so he doesn't want to reestablish his tree. Monocarp approves of any tree that has least tallness.
The stature of a tree is the most extreme profundity of the tree's vertices, and the profundity of a vertex is the number of edges in the way from the root to it. For instance, the profundity of vertex 1 is 0, since it's the root, and the profundity of every one of root's youngsters are 1.
Assist Monocarp with finding any tree with provided visiting request an and least tallness.
Input
The main line contains a solitary integer t (1≤t≤1000) — the number of experiments.
The main line of each experiment contains a solitary integer n (2≤n≤2⋅105) — the number of vertices in the tree.
The second line of each experiment contains n integers a1,a2,… ,an (1≤
It's surefire that the complete amount of n over experiments doesn't surpass 2⋅105.
Output
For each experiment print the base conceivable stature of a tree with the provided visiting request a.
Step by step
Solved in 4 steps with 1 images
