| Codeforces Round 225 (Div. 2) |
|---|
| Закончено |
Яхуб хочет потренироваться делать несколько дел одновременно. Для этого он хочет одновременно отсортировать n массивов по m целых чисел.
Яхуб может выбрать пару различных индексов, i и j (1 ≤ i, j ≤ m, i ≠ j). Затем в каждом из n массивов значения в позициях с номерами i и j меняются местами, только если значение в позиции i строго больше значения в позиции j.
Яхуб хочет найти такой массив пар различных индексов, что если выполнить описанную операцию с каждой парой из массива, просматривая пары в порядке их следования в массиве, то все n массивов в итоге будут отсортированы по невозрастанию, или по неубыванию (требуемый порядок дан во входных данных). Размер массива пар не может быть больше 
(не больше пар). Помогите Яхубу, найдите любой подходящий массив пар.
В первой строке содержатся три целых числа n (1 ≤ n ≤ 1000), m (1 ≤ m ≤ 100) и k. Число k равно 0, если массивы надо отсортировать по возрастанию, и 1, если их надо отсортировать по убыванию. Каждая строка i из следующих n строк содержит m целых чисел, разделенных пробелом, обозначающих i-ый массив. Для каждого элемента x массива i выполняется условие: 1 ≤ x ≤ 106.
В первой строке выведите целое число p — размер массива (p не больше ). В каждой из следующих p строк запишите два различных целых числа, i и j (1 ≤ i, j ≤ m, i ≠ j), обозначающих выбранные индексы.
Если правильных ответов несколько, можно вывести любой из них.
2 5 0
1 3 2 5 4
1 4 3 2 5
3
2 4
2 3
4 5
3 2 1
1 2
2 3
3 4
1
2 1
Рассмотрим первый тестовый пример. После первой операции массивы принимают вид [1, 3, 2, 5, 4] и [1, 2, 3, 4, 5]. После второй операции массивы принимают вид [1, 2, 3, 5, 4] и [1, 2, 3, 4, 5]. После третьей операции они принимают вид [1, 2, 3, 4, 5] и [1, 2, 3, 4, 5].
