501C.md (1920B)
1 Source: https://codeforces.com/problemset/problem/501/C 2 3 C. Misha and Forest 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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). 22 23 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. 24 25 Input 26 27 The first line contains integer *n* (1 ≤ *n* ≤ 216), the number of vertices in the graph. 28 29 The *i*-th of the next lines contains numbers *degree**i* and *s**i* (0 ≤ *degree**i* ≤ *n* - 1, 0 ≤ *s**i* < 216), separated by a space. 30 31 Output 32 33 In the first line print number *m*, the number of edges of the graph. 34 35 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*). 36 37 Edges can be printed in any order; vertices of the edge can also be printed in any order. 38 39 Examples 40 41 Input 42 43 ``` 44 3 45 2 3 46 1 0 47 1 0 48 ``` 49 50 Output 51 52 ``` 53 2 54 1 0 55 2 0 56 ``` 57 58 Input 59 60 ``` 61 2 62 1 1 63 1 0 64 ``` 65 66 Output 67 68 ``` 69 1 70 0 1 71 ``` 72 73 Note 74 75 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".