树是具有 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