学生 Vladislav 像往常一样在参加编程考试时完全没有准备。他收到了一个关于图表上某种奇怪算法的问题——这在现实生活中绝对没有用处。他让坐在他旁边的一个女孩借给他一些这道题的作弊卷,并发现了以下定义:
图G的最小生成树T是这样一棵树,它包含原始图G的所有顶点,并且其边的权重之和是所有此类树中可能的最小值。
Vladislav 绘制了一个具有 n 个顶点和 m 个边的图,其中不包含循环和多条边。他找到了它的最小生成树之一,然后为每条边写下了它的权重以及它是否包含在找到的树中。不幸的是,画图表的纸不见了,老师很生气,要求看原始图表。帮助 Vladislav 绘制一个图表,以便最小生成树的信息保持正确。
输入
输入的第一行包含两个整数 n 和 m ($$2 \leq n \leq 100\ 000, 1 \leq m \leq 100\ 000, n - 1 \leq m \leq \frac{n(n-1)}{2}$$) — 图中的顶点数和边数。
接下来的 m 行中的每一行都描述图的一条边,并由两个整数 aj 和 bj (1 ≤ aj ≤ 109, bj = {0, 1}) 组成。第一个数字是边的权重,如果该边包含在 Vladislav 找到的最小生成树中,则第二个数字等于 1,如果不包含,则等于 0。
保证恰好有 n - 1 个数字 {bj} 等于 1,并且恰好有 m - n + 1 个数字等于 0。
输出
如果 Vladislav 犯了一个错误并且这样的图不存在,则打印 - 1。
否则打印 m 行。在第 j 行上打印一对顶点 (uj, vj) (1 ≤ uj, vj ≤ n, uj ≠ vj),它们应由第 j 条边连接。边的编号顺序与输入中的顺序相同。由这些边确定的图必须是连通的,不包含环或多边,并且其 bj = 1 的边必须定义最小生成树。如果有多种可能的解决方案,请打印其中任何一个。
示例
输入 #1
4 5 2 1 3 1 4 0 1 1 5 0
输出 #1
2 4 1 4 3 4 3 1 3 2
输入 #2
3 3 1 0 2 1 3 1
输出 #2
-1