Задача №1869. Префикс-функция
На досуге Вася занимается изучением префикс-функции. Для начала опишем, что это такое: пусть дана строка \(s\). Обозначим её префикс длины \(i\) как \(p_i\), а суффикс длины \(i\) как \(s_i\). Тогда префикс-функцией строки \(s\) называется такое максимальное число \(\pi(s)\), меньшее её длины, что \(p_{\pi(s)} = s_{\pi(s)}\).
Вася не слишком аккуратен, поэтому его компьютер часто заражается вирусами. Последний раз вирус испортил файл со строкой, префикс-функцию префиксов которой Вася изучал последнюю неделю. К счастью, некоторые значения префикс-функции сохранились.
Вася хочет восстановить строку \(s\). Он сомневается, что удастся сделать это однозначно, поэтому для определённости его интересует лексикографически минимальная строка с таким набором известных префикс-функций префиксов.
Напишите программу, которая поможет Васе. В исходной строке \(s\) было использовано много разных символов, например, китайских иероглифов. Поэтому при восстановлении можете считать, что у вас в наличии есть столько символов, сколько понадобится, и все они пронумерованы натуральными числами, начиная с единицы.
Входной файл содержит несколько тестов. Каждый из них начинается строкой, содержащей единственное целое число \(n\) — длину строки. Вторая строка теста содержит \(n\) целых чисел — значения \(\pi(p_1), \pi(p_2), \ldots, \pi(p_n)\) (\(-1 \le \pi(p_i) \le n\)). Те значения, которые не сохранились, обозначены \(-1\).
Файл завершается строкой с одним нулём, который не является тестом и который не нужно обрабатывать. Сумма \(n\) по всем тестам в одном входном файле не превысит \(2\,000\).
Для каждого теста выведите лексикографически минимальную строку, подходящую под соответствующий набор значений префикс-функции, либо сообщите, что такой строки не существует.
Следуйте формату вывода, приведённому в примере, как можно точнее.
7 0 0 1 0 1 2 3 4 -1 -1 -1 3 2 1 0 0
Case #1: The minimal string is 1 2 1 3 1 2 1 Case #2: The minimal string is 1 1 1 1 Case #3: There is no such string