D. Восстановление функционального графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Функциональный граф — это ориентированный граф, каждая вершина которого имеет исходящую степень 1. Петли разрешены.

Некоторые вершины функционального графа лежат на циклах. Из остальных же вершин можно попасть в цикл, сделав конечное число переходов по рёбрам (мы рассматриваем только конечные функциональные графы).

Дадим вершинам функционального графа две характеристики. precyclei — количество ребёр, по которым необходимо перейти, начиная из вершины i, чтобы попасть в вершину, принадлежащую циклу (ноль, если вершина уже принадлежит циклу), и cyclei — количество вершин в цикле, в который мы попадём.

Вам дана информация о вершинах некоторого функционального графа. Для каждой вершины известны значения precyclei и cyclei, однако вместо некоторых из этих значений могут стоять знаки вопроса. Это означает, что соответствующее значение может быть любым.

Восстановите любой функциональный граф, подходящий под заданное описание, либо сообщите, что такого графа не существует.

Входные данные

На первой строке записано целое число n (1 ≤ n ≤ 300) — количество вершин графа. Далее в n строках записаны два значения — precyclei (0 ≤ precyclei ≤ n - 1) и cyclei (1 ≤ cyclei ≤ n). Вместо некоторых из этих значений могут стоять знаки вопроса.

Выходные данные

Если искомого графа не существует, на единственной строке выведите -1.

В противном случае, выведите n чисел. i-е число — номер вершины, в которую ведёт ребро, исходящее из вершины i.

Вершины выведенного графа должны следовать в том же порядке, в котором они были заданы во входных данных.

Если существует несколько решений, выведите любое.

Примеры
Входные данные
3
0 3
0 3
? ?
Выходные данные
2 3 1
Входные данные
5
3 2
? ?
? ?
? ?
? ?
Выходные данные
5 3 2 2 4
Входные данные
8
? 3
? ?
0 2
0 2
0 3
0 3
0 3
3 3
Выходные данные
5 1 4 3 6 7 5 2
Входные данные
1
? ?
Выходные данные
1
Входные данные
6
0 3
0 3
0 3
0 3
0 3
0 3
Выходные данные
2 3 1 5 6 4
Входные данные
2
1 1
1 1
Выходные данные
-1