384B.md (2355B)
1 Source: https://codeforces.com/problemset/problem/384/B 2 3 B. Multitasking 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 Iahub wants to enhance his multitasking abilities. In order to do this, he wants to sort *n* arrays simultaneously, each array consisting of *m* integers. 22 23 Iahub can choose a pair of distinct indices *i* and *j* (1 ≤ *i*, *j* ≤ *m*, *i* ≠ *j*). Then in each array the values at positions *i* and *j* are swapped only if the value at position *i* is strictly greater than the value at position *j*. 24 25 Iahub wants to find an array of pairs of distinct indices that, chosen in order, sort all of the *n* arrays in ascending or descending order (the particular order is given in input). The size of the array can be at most  (at most  pairs). Help Iahub, find any suitable array. 26 27 Input 28 29 The first line contains three integers *n* (1 ≤ *n* ≤ 1000), *m* (1 ≤ *m* ≤ 100) and *k*. Integer *k* is 0 if the arrays must be sorted in ascending order, and 1 if the arrays must be sorted in descending order. Each line *i* of the next *n* lines contains *m* integers separated by a space, representing the *i*-th array. For each element *x* of the array *i*, 1 ≤ *x* ≤ 106 holds. 30 31 Output 32 33 On the first line of the output print an integer *p*, the size of the array (*p* can be at most ). Each of the next *p* lines must contain two distinct integers *i* and *j* (1 ≤ *i*, *j* ≤ *m*, *i* ≠ *j*), representing the chosen indices. 34 35 If there are multiple correct answers, you can print any. 36 37 Examples 38 39 Input 40 41 ``` 42 2 5 0 43 1 3 2 5 4 44 1 4 3 2 5 45 ``` 46 47 Output 48 49 ``` 50 3 51 2 4 52 2 3 53 4 5 54 ``` 55 56 Input 57 58 ``` 59 3 2 1 60 1 2 61 2 3 62 3 4 63 ``` 64 65 Output 66 67 ``` 68 1 69 2 1 70 ``` 71 72 Note 73 74 Consider the first sample. After the first operation, the arrays become [1, 3, 2, 5, 4] and [1, 2, 3, 4, 5]. After the second operation, the arrays become [1, 2, 3, 5, 4] and [1, 2, 3, 4, 5]. After the third operation they become [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5].