| Codeforces Round 453 (Div. 1) |
|---|
| Закончено |
Саша участвует в соревновании по программированию. В очередной задаче ей нужно уметь проверять корневые деревья на изоморфизм. Она никогда не сталкивалась с этой задачей раньше, но, будучи опытной участницей, быстро догадалась, что для этого стоит сопоставить каждому дереву некоторую последовательность и сравнивать уже эти последовательности, а не деревья. Саша хочет поставить в соответствие дереву такую последовательность a0, a1, ..., ah, где h — высота дерева, что ai равно числу вершин, находящихся на расстоянии i рёбер от корня.
К сожалению, в этот раз интуиция подвела Сашу, и оказалось, что такая последовательность может не однозначно задавать дерево. Чтобы это показать, вы должны написать программу, которая по заданной последовательности ai предоставит два неизоморфных корневых дерева, которым соответствует такая последовательность, или скажет, что такое дерево единственно.
Два корневых дерева считаются изоморфными, если можно так перенумеровать вершины одного из них, чтобы оно стало равно второму, при этом корень первого дерева должен получить номер корня второго дерева.
Высотой дерева будем называть наибольшее число рёбер в пути от корня до какой либо другой вершины.
Первая строка ввода содержит единственное целое число h (2 ≤ h ≤ 105) — высоту дерева.
Вторая строка содержит h + 1 целое число — последовательность a0, a1, ..., ah (1 ≤ ai ≤ 2·105). Сумма всех чисел ai не превосходит 2·105. Гарантируется, что последовательности соответствует хотя бы одно дерево.
Если последовательность однозначно задаёт дерево, выведите «perfect».
Иначе в первую строку выведите «ambiguous». Во вторую и третью строчки выведите описания двух деревьев в следующем формате: в одну строку выведите 
чисел, k-е из них должно задавать предка вершины k или быть равным нулю, если k-я вершина является корнем дерева.
Эти два дерева должны быть неизоморфны и должны соответствовать заданной последовательности.
2
1 1 1
perfect
2
1 2 2
ambiguous
0 1 1 3 3
0 1 1 3 2
Единственное дерево к первому примеру и два выведенных дерева ко второму:
