H. Новый Год и забытое дерево
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Деревом называется связный неориентированный граф из n вершин и n - 1 ребра. Вершины пронумерованы от 1 до n.

Лимак — белый медвежонок, и его медвежья семья каждый год собирает новогоднее дерево. Год назад дерево получилось особенно замечательным, поэтому они решили запомнить его и собрать такое же в этом году. Эта миссия была поручена Лимаку.

Запомнить всё дерево и не забыть в течение года было бы слишком сложно, поэтому Лимак решил записать его рёбра в своем блокноте. Он взял ручку и записал n - 1 строку, по два целых числа в каждой — индексы двух вершин, соединённых общим ребром.

И вот новый год уже совсем близко, семья попросила Лимака восстановить прошлогоднее дерево. И тут начались проблемы. Год назад он был ещё очень маленьким медвежонком, и не знал ни цифр, ни алфавита, поэтому он просто заменил все цифры на вопросительные знаки — единственный известный ему символ. Это означает, что для каждого индекса вершины, записанного в его блокноте, он знает только количество цифр в его записи. По крайней мере, он уверен, что все индексы записывались без ведущих нулей.

Лимак очень не хочет всех разочаровать, поэтому он попросил вас построить какое-нибудь дерево, отвечающее его записям в блокноте. Найдите такое дерево и выведите его рёбра в любом порядке. Если Лимак допустил ошибку, и подходящего дерева не существует, то выведите "-1" (без кавычек).

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

В первой строке записано единственное число n (2 ≤ n ≤ 200 000) — количество вершин в прошлогоднем дереве.

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

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

Если подходящего дерева нет, выведите "-1" (без кавычек).

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

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