У Монокарпа было дерево из \(n\) вершин с корнем в вершине \(1\). Он решил изучить алгоритм BFS (Поиск в ширину), и поэтому запустил BFS на своем дереве, стартуя с корня. Упрощенно, BFS можно описать следующим псевдокодом:
a = [] # порядок, в котором вершины обработались
q = Queue()
q.put(1) # кладем корень в конец очереди
while not q.empty():
k = q.pop() # достаем вершину из начала очереди
a.append(k) # кладем k в конец последовательности, описывающей порядок посещения вершин
for y in g[k]: # g[k] — это список всех детей вершины k, отсортированный в порядке возрастания
q.put(y)
Монокарп был так восхищен алгоритмом BFS, что в результате потерял свое дерево. К счастью, у него осталась последовательность вершин в порядке их посещения алгоритмом BFS (массив a из псевдокода). Монокарп знает, что каждая вершина была посещена ровно один раз (так как они кладутся и забираются из очереди ровно один раз). Также он знает, что все дети каждой вершины были просмотрены в порядке возрастания.
Монокарп понимает, что есть много деревьев (в общем случае) с одинаковым порядком посещения \(a\), поэтому даже не надеется восстановить свое дерево. Монокарпа устроит любое дерево минимально возможной высоты.
Высота дерева — это максимум среди глубин вершин дерева, и глубина вершины — это количество дуг на пути от корня до этой вершины. Например, глубина вершины \(1\) равна \(0\), так как она является корнем, а глубина любого из детей корня равна \(1\).
Помогите Монокарпу найти любое дерево с заданным порядком посещения \(a\) и минимальной высотой.
Примечание
В первом наборе входных данных, есть только одно дерево с заданным порядком посещения:
Во втором наборе, также есть только одно дерево с заданным порядком посещения:
В третьем наборе, оптимальное дерево с заданным порядком посещения изображено ниже:
