← 返回题目列表

Codeforces · 501/C

C. 米莎和森林

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

让我们将森林定义为无向无环图(也没有循环和平行边)。有一天,Misha 玩起了由 n 个顶点组成的森林。对于从 0 到 n - 1 的每个顶点 v,他写下两个整数: Degreev 和 sv,第一个整数是与顶点 v 相邻的顶点数,第二个整数是与 v 相邻的顶点数的异或和(如果没有相邻顶点,他写下 0)。

第二天,Misha 不记得他最初拥有的图表是什么。不过,Misha 的左值是 Degreev 和 sv。帮助他求出边的数量以及初始图的边数。保证存在与米莎所写数字相对应的森林。

输入

第一行包含整数 n (1 ≤ n ≤ 216),即图中的顶点数。

接下来的第 i 行包含数字 Degreei 和 si (0 ≤ Degreei ≤ n - 1, 0 ≤ si < 216),以空格分隔。

输出

在第一行打印数字 m,即图形的边数。

接下来打印 m 行,每行包含两个不同的数字 a 和 b (0 ≤ a ≤ n - 1, 0 ≤ b ≤ n - 1),对应于边 (a, b)。

边缘可以按任意顺序打印;边缘的顶点也可以按任何顺序打印。

示例

输入 #1

3
2 3
1 0
1 0

输出 #1

2
1 0
2 0

输入 #2

2
1 1
1 0

输出 #2

1
0 1

注意

数字的异或和是数字按位相加模 2 的结果。此操作存在于许多现代编程语言中。例如,在 C++、Java 和 Python 语言中,它表示为“^”,在 Pascal 中表示为“xor”。