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".

Difficulty: interview

Starter code:

Solutions:
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])



#!/usr/bin/env python3

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)



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()

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[0]
    del deg1[0]
    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)
    
    



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)
    
    



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])

print(degsum//2)

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]
    print(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
    
    



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])

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()

def main():
    n, l, ones, j = int(input()), [], [], 0
    for i in range(n):
        degree, s = list(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)


def __starting_point():
    main()

__starting_point()

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()

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):
    # correct, but slow
    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()

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)


# 501C

__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)

# 501C

__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)
  counter += 1
  ans += '\n' + str(s) + ' ' + str(v)
  degrees[s] -= 1
  if degrees[s] == 1:
    queue.append(s)

print(str(counter) + ans)

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])


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)




# Made By Mostafa_Khaled


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])

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)

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())
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)

'''
9
2 5
4 3
7 6
8 3
5 0
6 1
3 9
1 0
9 0
'''

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 = g[1].pop()
    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)

'''
9
2 5
4 3
7 6
8 3
5 0
6 1
3 9
1 0
9 0
'''

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())
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])






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])