Good Bye 2015 |
---|
Закончено |
Деревом называется связный неориентированный граф из 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
Название |
---|