← 返回题目列表

Codeforces · 611/H

H. 新年和被遗忘的树

中文机器翻译题面 查看原题

树是具有 n - 1 条边的连通无向图,其中 n 表示顶点数。顶点编号为 1 到 n。

Limak 是一只小北极熊。他的熊家每年都会准备一棵新年树。一年前,他们的树比平时更棒。因此,他们决定明年再种植同样的树。利马克负责记住那棵树。

记住一整棵树是很困难的。利马克决定在他的笔记本上描述它。他拿起笔写了 n - 1 行,每行都有两个整数——由一条边连接的两个顶点的索引。

现在,新年即将来临,利马克被要求重建那棵树。当然,有一个问题。一年前,他还是一只小熊,不认识数字和字母,所以他只是用问号代替了每个数字——这是他唯一认识的字符。这意味着,对于他笔记中的任何顶点索引,他只知道其中的位数。至少他知道没有前导零。

Limak 不想让大家失望。请记下他的笔记并重建一棵新年树。找到任何与 Limak 的记录匹配的树,并以任意顺序打印其边缘。也有可能 Limak 犯了一个错误,并且没有合适的树 - 在这种情况下打印“-1”(不带引号)。

输入

第一行包含一个整数 n (2 ≤ n ≤ 200 000) — 顶点数。

接下来的 n - 1 行中的每一行都包含两个以空格分隔的非空字符串,均仅包含问号。任何字符串的字符数都不会超过 n 中的位数。

输出

如果没有树匹配 Limak 的记录,则打印唯一带有“-1”的行(不带引号)。

否则,描述与 Limak 的笔记匹配的任何树。打印 n - 1 行,每行有两个空格分隔的整数——由边连接的顶点的索引。您可以按任何顺序打印边缘。

示例

输入 #1

12
? ?
? ?
? ?
? ??
?? ?
?? ??
? ??
? ?
? ?
? ?
? ?

输出 #1

3 1
1 6
9 1
2 10
1 7
8 1
1 4
1 10
5 1
10 11
12 1

输入 #2

12
?? ??
? ?
? ?
? ??
?? ?
?? ??
? ??
? ?
? ?
?? ??
? ?

输出 #2

-1