Let's define a forest as a non-directed acyclic graph (also without loops and parallel edges). One day Misha played with the forest consisting of n vertices. For each vertex v from 0 to n - 1 he wrote down two integers, degree_{v} and s_{v}, were the first integer is the number of vertices adjacent to vertex v, and the second integer is the XOR sum of the numbers of vertices adjacent to v (if there were no adjacent vertices, he wrote down 0). 

Next day Misha couldn't remember what graph he initially had. Misha has values degree_{v} and s_{v} left, though. Help him find the number of edges and the edges of the initial graph. It is guaranteed that there exists a forest that corresponds to the numbers written by Misha.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2^16), the number of vertices in the graph.

The i-th of the next lines contains numbers degree_{i} and s_{i} (0 ≤ degree_{i} ≤ n - 1, 0 ≤ s_{i} < 2^16), separated by a space.


-----Output-----

In the first line print number m, the number of edges of the graph.

Next print m lines, each containing two distinct numbers, a and b (0 ≤ a ≤ n - 1, 0 ≤ b ≤ n - 1), corresponding to edge (a, b).

Edges can be printed in any order; vertices of the edge can also be printed in any order.


-----Examples-----
Input
3
2 3
1 0
1 0

Output
2
1 0
2 0

Input
2
1 1
1 0

Output
1
0 1



-----Note-----

The XOR sum of numbers is the result of bitwise adding numbers modulo 2. This operation exists in many modern programming languages. For example, in languages C++, Java and Python it is represented as "^", and in Pascal — as "xor".

Source: codeforces | Difficulty: MEDIUM
Tags: Constructive algorithms

Sorting

Greedy algorithms

Tree algorithms

Data structures


Solutions:
n = int(input())
verts = []
e = []
for i in range(n):
	inp = [*map(int, input().split(' '))]
	verts.append([i] + inp)
leavesQ = list(filter(lambda v: v[1] == 1, verts))
while len(leavesQ) > 0:
	l = leavesQ.pop()
	if l[1] != 1:
		continue
	l2 = verts[l[2]]
	e.append([l[0], l2[0]])
	l[1] -= 1
	l2[1] -= 1
	l2[2] ^= l[0]
	if l2[1] == 1:
		leavesQ.append(l2)
print(len(e))
for [x, y] in e:
	print(x, y)


from heapq import heappush, heappop
queue = []
degree = []
s = []
ans = []
n = int(input())
used = [False for i in range(n)]
for i in range(n):
	(a, b) = list(map(int, input().split()))
	degree.append(a)
	s.append(b)
	heappush(queue, (a, i))
while queue:
	el = heappop(queue)
	vert = el[1]
	if used[vert]:
		continue
	used[vert] = True
	if degree[vert] == 0:
		continue
	other = s[vert]
	ans.append((vert, other))
	s[other] ^= vert
	degree[other] -= 1
	heappush(queue, (degree[other], other))
print(len(ans))
for el in ans:
	print(el[0], el[1])


n = int(input())
l = []
stack = []
for i in range(n):
	(d, s) = map(int, input().split())
	if d == 1:
		stack.append(i)
	l.append([d, s])
c = 0
edges = ''
while stack:
	i = stack.pop(0)
	(d, s) = l[i]
	if d == 0:
		continue
	(dd, ss) = l[s]
	if dd == 2:
		stack.append(s)
	l[s] = [dd - 1, ss ^ i]
	edges += str(i) + ' ' + str(s) + '\n'
	c += 1
print(c)
print(edges)


n = int(input())
f = [list(map(int, input().split())) for i in range(n)]
deg1 = []
edges = []
for i in range(n):
	if f[i][0] == 1:
		deg1.append(i)
while len(deg1):
	i = deg1.pop()
	if f[i][0] == 0:
		continue
	edges.append([i, f[i][1]])
	f[i][0] -= 1
	f[f[i][1]][0] -= 1
	f[f[i][1]][1] ^= i
	if f[f[i][1]][0] == 1:
		deg1.append(f[i][1])
print(len(edges))
for e in edges:
	print(e[0], e[1])


from collections import deque
n = int(input())
process = deque()
vs = []
for i in range(n):
	(d, s) = list(map(int, input().split()))
	if d == 1:
		process.append(i)
	vs.append((d, s))
edges = []
while process:
	a = process.popleft()
	(d, s) = vs[a]
	if d == 0:
		continue
	(dd, ss) = vs[s]
	vs[s] = (dd - 1, ss ^ a)
	if dd == 2:
		process.append(s)
	edges.append((a, s))
print(len(edges))
for (a, b) in edges:
	print(a, b)


def main():
	n = int(input())
	(ones, l) = (set(), [])
	for i in range(n):
		(degree, s) = list(map(int, input().split()))
		if degree == 1:
			ones.add(i)
		l.append((degree, s))
	res = []
	while ones:
		i = ones.pop()
		(degree_i, j) = l[i]
		(degree_j, s) = l[j]
		res.append(' '.join((str(i), str(j))))
		if degree_j == 1:
			ones.remove(j)
		else:
			degree_j -= 1
			if degree_j == 1:
				ones.add(j)
			l[j] = (degree_j, s ^ i)
	print(len(res))
	print('\n'.join(res))

def __starting_point():
	main()
__starting_point()


n = int(input())
v = []
deg1 = []
degsum = 0
has_v = [True] * n
for i in range(n):
	(d, s) = list(map(int, input().split()))
	degsum += d
	if d == 1:
		deg1.append(i)
	if d == 0:
		has_v[i] = False
	v.append([d, s])
edge = []
while deg1 != []:
	f = deg1.pop()
	if has_v[f] is False:
		continue
	v[f][0] -= 1
	has_v[f] = False
	t = v[f][1]
	edge.append([f, t])
	v[t][0] -= 1
	v[t][1] ^= f
	if v[t][0] == 1:
		deg1.append(t)
	elif v[t][0] == 0:
		has_v[t] = False
print(degsum // 2)
for (f, t) in edge:
	print(f, t)


import math
from collections import Counter
import math
n = int(input())
deg = [0] * n
ss = [0] * n
q = []
for i in range(n):
	(deg[i], ss[i]) = map(int, input().split())
	if deg[i] == 1:
		q.append(i)
edges = []
while q:
	leaf = q.pop()
	if deg[leaf] == 0:
		continue
	v = ss[leaf]
	edges.append((leaf, v))
	deg[v] -= 1
	ss[v] = ss[v] ^ leaf
	if deg[v] == 1:
		q.append(v)
print(len(edges))
for i in edges:
	print(*i)


n = int(input())
deg2vs = {}
ss = [0] * n
degs = [0] * n
for i in range(n):
	(degs[i], ss[i]) = list(map(int, input().split()))
	if degs[i] > 0:
		if degs[i] not in deg2vs:
			deg2vs[degs[i]] = set()
		deg2vs[degs[i]].add(i)
edges = []
while len(deg2vs) != 0:
	leaves = deg2vs.pop(1)
	for leaf in leaves:
		if degs[leaf] == 0:
			continue
		v = ss[leaf]
		edges.append((leaf, v))
		v_deg = degs[v]
		if v_deg > 1:
			deg2vs[v_deg].remove(v)
			if len(deg2vs[v_deg]) == 0:
				deg2vs.pop(v_deg)
		ss[v] = ss[v] ^ leaf
		degs[v] -= 1
		if degs[v] > 0:
			if degs[v] not in deg2vs:
				deg2vs[degs[v]] = set()
			deg2vs[degs[v]].add(v)
print(len(edges))
for edge in edges:
	print(edge[0], edge[1])


from sys import stdin, stdout, setrecursionlimit
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
from bisect import bisect_right as br, bisect_left as bl
import heapq
n = it()
v = []
for _ in range(n):
	v.append(mp())
q = deque()
for i in range(n):
	if v[i][0] == 1:
		q.append(i)
ans = []
while q:
	ver = q.popleft()
	if not v[ver][0]:
		continue
	ans.append([ver, v[ver][1]])
	v[v[ver][1]][0] -= 1
	v[v[ver][1]][1] ^= ver
	if v[v[ver][1]][0] == 1:
		q.append(v[ver][1])
print(len(ans))
for i in range(len(ans)):
	print(*ans[i])


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def main():
	n = int(input())
	arr = []
	q = deque()
	for _ in range(n):
		(a, b) = map(int, input().split())
		arr.append([a, b])
		if a == 1:
			q.append(_)
	ans = []
	while q:
		x = q.popleft()
		if arr[x][0] == 1:
			ans.append((x, arr[x][1]))
		else:
			continue
		y = arr[x][1]
		arr[y][0] -= 1
		arr[y][1] ^= x
		if arr[y][0] == 1:
			q.append(y)
	print(len(ans))
	for _ in ans:
		print(*_)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
d = []
s = []
sm = 0
alone = []
for i in range(n):
	(de, se) = map(int, input().split())
	d.append(de)
	s.append(se)
	if de == 1:
		alone.append(i)
	sm += de
print(sm // 2)
while alone:
	v = alone.pop()
	if d[v] == 1:
		print(v, s[v])
		s[s[v]] ^= v
		d[s[v]] -= 1
		if d[s[v]] == 1:
			alone.append(s[v])


def main():
	(n, l, ones) = (int(input()), [], [])
	for i in range(n):
		(degree, s) = list(map(int, input().split()))
		l.append((degree, s))
		if degree == 1:
			ones.append(i)
	res = []
	while ones:
		i = ones.pop()
		(degree, j) = l[i]
		if degree == 1:
			res.append(' '.join((str(i), str(j))))
			(degree, s) = l[j]
			s ^= i
			degree -= 1
			l[j] = (degree, s)
			if degree == 1:
				ones.append(j)
	print(len(res))
	print('\n'.join(res))

def __starting_point():
	main()
__starting_point()


from queue import PriorityQueue
N = int(input())
v = list()
Q = list()
for i in range(N):
	(s, k) = input().split()
	v.append((int(s), int(k)))
	if int(s) == 1:
		Q.append(i)
edge = list()
while len(Q) > 0:
	u = Q.pop()
	if v[u][0] == 0:
		continue
	g = v[u][1]
	edge.append((u, g))
	v[g] = (v[g][0] - 1, v[g][1] ^ u)
	if v[g][0] == 1:
		Q.append(g)
print(len(edge))
for (i, j) in edge:
	print(i, j)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from queue import Queue as Q
q = Q()
(n,) = I()
l = []
x = [0] * (n + 10)
d = [0] * (n + 10)
for i in range(n):
	(a, b) = I()
	x[i] = b
	d[i] = a
	if a == 1:
		q.put(i)
e = []
while not q.empty():
	p = q.get()
	par = x[p]
	if d[p] == 1:
		if p != par:
			e.append([p, par])
		x[par] ^= p
		d[par] -= 1
		d[p] -= 1
		if d[par] == 1:
			q.put(par)
print(len(e))
for i in e:
	if i[0] != i[1]:
		print(*i)


n = int(input())
ss = [0] * n
degs = [0] * n
leaves = []
for i in range(n):
	(degs[i], ss[i]) = list(map(int, input().split()))
	if degs[i] == 1:
		leaves.append(i)
edges = []
while len(leaves) != 0:
	leaf = leaves.pop()
	if degs[leaf] == 0:
		continue
	v = ss[leaf]
	edges.append((leaf, v))
	v_deg = degs[v]
	ss[v] = ss[v] ^ leaf
	degs[v] -= 1
	if degs[v] == 1:
		leaves.append(v)
print(len(edges))
for edge in edges:
	print(edge[0], edge[1])


__author__ = 'artyom'
read = lambda : map(int, input().split())
n = int(input())
graph = [set() for _ in range(n)]
degrees = []
adj = []
queue = []
for i in range(n):
	(degree, s) = read()
	degrees.append(degree)
	adj.append(s)
	if degree == 1:
		queue.append(i)
counter = 0
ans = ''
while queue:
	v = queue.pop()
	if degrees[v] == 0:
		continue
	s = adj[v]
	for u in graph[v]:
		s ^= u
	graph[s].add(v)
	graph[v].add(s)
	counter += 1
	ans += '\n' + str(s) + ' ' + str(v)
	degrees[s] -= 1
	if degrees[s] == 1:
		queue.append(s)
print(str(counter) + ans)


n = int(input())
d = []
v = []
for i in range(n):
	(a, b) = map(int, input().split())
	v.append([a, b, i])
g = dict()
for i in range(n + 20):
	g[i] = set()
for i in v:
	if i[0] in g:
		g[i[0]].add(i[2])
	else:
		g[i[0]] = set()
		g[i[0]].add(i[2])
ans = []
while len(g[1]) > 0:
	i = 0
	for x in g[1]:
		i = x
		break
	a = v[i][2]
	b = v[i][1]
	g[v[a][0]].discard(v[a][2])
	g[v[a][0] - 1].add(v[a][2])
	v[a][0] -= 1
	g[v[b][0]].discard(v[b][2])
	g[v[b][0] - 1].add(v[b][2])
	v[b][0] -= 1
	v[b][1] ^= a
	ans.append((a, b))
print(len(ans))
for i in ans:
	print(*i)


def main():
	(n, l, ones, j) = (int(input()), [], [], 0)
	for i in range(n):
		(degree, s) = map(int, input().split())
		l.append((degree, s))
		j += degree
		if degree == 1:
			ones.append(i)
	print(j // 2)
	while ones:
		i = ones.pop()
		(degree, j) = l[i]
		if degree == 1:
			print(i, j)
			(degree, s) = l[j]
			s ^= i
			degree -= 1
			l[j] = (degree, s)
			if degree == 1:
				ones.append(j)
main()


n = int(input())
stack_leaves = []
deg = [0] * n
s = [0] * n
summ = 0
for i in range(n):
	(deg[i], s[i]) = map(int, input().split())
	summ += deg[i]
	if deg[i] == 1:
		stack_leaves.append(i)
print(summ // 2)
while stack_leaves:
	x = stack_leaves.pop()
	if deg[x] != 0:
		print(x, s[x])
		deg[s[x]] -= 1
		s[s[x]] ^= x
		if deg[s[x]] == 1:
			stack_leaves.append(s[x])


import math, string, itertools, fractions, heapq, collections, re, array, bisect
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict

def main2(n, d, s, info=0):
	edges = []
	m = mm = sum(d) // 2
	while m > 0:
		f = [x for x in zip(d, list(range(n))) if x[0] == 1]
		for (_, i) in f:
			if d[i] == 1:
				d[i] = 0
				d[s[i]] -= 1
				s[s[i]] ^= i
				m -= 1
				edges.append([i, s[i]])
	print(mm)
	for (u, v) in edges:
		print(u, v)

def main(n, d, s, info=0):
	edges = []
	curr = []
	for i in range(n):
		if d[i] == 1:
			curr.append(i)
	while len(curr):
		i = curr.pop()
		if d[i] == 1:
			d[i] = 0
			d[s[i]] -= 1
			s[s[i]] ^= i
			edges.append([i, s[i]])
			if d[s[i]] == 1:
				curr.append(s[i])
	print(len(edges))
	for (u, v) in edges:
		print(u, v)

def main_input(info=0):
	n = int(input())
	(d, s) = (list(range(n)), list(range(n)))
	for i in range(n):
		(d[i], s[i]) = list(map(int, input().split()))
	main(n, d, s, info=info)

def __starting_point():
	main_input()
__starting_point()


(n, st, xors, sumst, buf) = (int(input()), [], [], 0, [])
for i in range(n):
	s = input().split()
	st.append(int(s[0]))
	xors.append(int(s[1]))
	sumst += st[i]
	if st[i] == 1:
		buf.append(i)
if sumst % 2 != 0:
	print('0')
	return
print(sumst // 2)
while buf:
	v = buf.pop()
	if st[v] == 1:
		print(str(v) + ' ' + str(xors[v]))
		xors[xors[v]] ^= v
		st[xors[v]] -= 1
		if st[xors[v]] == 1:
			buf.append(xors[v])


R = lambda : map(int, input().split())
n = int(input())
(degs, xors) = ([0] * (2 ** 16 + 1), [0] * (2 ** 16 + 1))
edges = []
for curr in range(n):
	(degs[curr], xors[curr]) = R()
q = []
for curr in range(n):
	if degs[curr] == 1:
		q.append(curr)
while q:
	curr = q.pop()
	if degs[curr] != 1:
		continue
	neighbor = xors[curr]
	edges.append((min(curr, neighbor), max(curr, neighbor)))
	degs[neighbor] -= 1
	xors[neighbor] ^= curr
	if degs[neighbor] == 1:
		q.append(neighbor)
filter(lambda p: p[0] < p[1], edges)
print(len(edges))
for (u, v) in edges:
	if u < v:
		print(u, v)


n = int(input())
(degrees, mas, masiv) = (0, [], [])
for i in range(n):
	(degree, s) = map(int, input().split())
	if degree == 1:
		masiv.append(i)
	degrees += degree
	mas.append([degree, s])
print(degrees // 2)
while masiv:
	last_elem = masiv.pop(-1)
	relax = mas[last_elem][1]
	if mas[last_elem][0] != 1:
		continue
	mas[last_elem][0] -= 1
	mas[last_elem][1] ^= relax
	mas[relax][0] -= 1
	mas[relax][1] ^= last_elem
	print(relax, last_elem)
	if mas[relax][0] == 1:
		masiv.append(relax)


from collections import defaultdict

def main():
	n = int(input())
	bydegree = defaultdict(set)
	bys = defaultdict(set)
	l = []
	for i in range(n):
		(degree, s) = list(map(int, input().split()))
		bydegree[degree].add(i)
		bys[s].add(i)
		l.append((degree, s))
	res = []
	ones = bydegree[1]
	while ones:
		i = ones.pop()
		(degree_i, j) = l[i]
		(degree_j, s) = l[j]
		res.append(' '.join((str(i), str(j))))
		bydegree[degree_j].remove(j)
		degree_j -= 1
		bydegree[degree_j].add(j)
		l[j] = (degree_j, s ^ i)
	print(len(res))
	print('\n'.join(res))

def __starting_point():
	main()
__starting_point()