问题 5174 --天晨与森林

5174: 天晨与森林★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 73  解决: 17
[提交][状态][命题人:]

题目描述

让我们将森林定义为无向无环图。天晨获得了一片由 n 个顶点组成的森林,对于编号为 0 到 n-1 的每个顶点,他知道两个信息 di 与 si,其中 di 代表这个顶点的度, si 代表所有与该顶点有边相连的顶点的编号异或后的结果。请你帮助天晨把这片森林还原出来。

无向图中,每个定点的度,指的是其他顶点和该顶点相连的边数

异或运算指的是位运算,不妨用^表示异或运算,则0^0=1^1=0, 0^1=1^0=1

输入

第一行包含一个整数 n(1<=n<=65536),代表顶点数量。接下来的 n 行,每行包括两个数字 di 与 si(0<=di<=n-1,0<=si<65536),分别代表这个顶点的度以及所有与该顶点相邻的顶点的编号异或后的结果。

输出

第一行包含一个整数 m,代表森林的边数。接下来的 m 行,每行包括两个整数 ai 和 bi(0<=ai<bi<=n-1),对应顶点 ai与顶点 bi之间有一条边。输出时,先根据ai从小到大输出,如果两条边的ai相同,则再按bi从小到大输出
样例输入
Copy
3
2 3
1 0
1 0
样例输出
Copy
2
0 1
0 2

提示

样例2输入

2
1 1
1 0

样例2输出

1
0 1

注释:

对于样例1而言,点0和点1之间存在一条边,点0与点2之间存在一条边。

来源

[提交][状态]