← 返回题目列表

Codeforces · 605/B

B. 懒惰的学生

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

学生 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