codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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