← 返回题目列表

Codeforces · 384/B

B. 多任务处理

中文机器翻译题面 查看原题

Iahub 希望增强他的多任务处理能力。为了做到这一点,他想要同时对 n 个数组进行排序,每个数组由 m 个整数组成。

Iahub 可以选择一对不同的索引 i 和 j (1 ≤ i, j ≤ m, i ≠ j)。然后,在每个数组中,仅当位置 i 处的值严格大于位置 j 处的值时,才会交换位置 i 和 j 处的值。

Iahub 希望找到一个由不同索引对组成的数组,按顺序选择这些索引,按升序或降序对所有 n 个数组进行排序(特定顺序在输入中给出)。数组的大小最多为 $$\frac{m(m-1)}{2}$$ (最多 $$\frac{m(m-1)}{2}$$ 对)。帮助Iahub,找到任何合适的阵列。

输入

第一行包含三个整数 n (1 ≤ n ≤ 1000)、m (1 ≤ m ≤ 100) 和 k。如果数组必须按升序排序,则整数 k 为 0;如果数组必须按降序排序,则整数 k 为 1。接下来的n行中的每一行i包含m个由空格分隔的整数,代表第i个数组。对于数组 i 的每个元素 x,1 ≤ x ≤ 106 成立。

输出

在输出的第一行打印一个整数 p,即数组的大小(p 最多可以是 $$\frac{m(m-1)}{2}$$)。接下来的 p 行中的每一行都必须包含两个不同的整数 i 和 j (1 ≤ i, j ≤ m, i ≠ j),表示所选索引。

如果有多个正确答案,您可以打印任何一个。

示例

输入 #1

2 5 0
1 3 2 5 4
1 4 3 2 5

输出 #1

3
2 4
2 3
4 5

输入 #2

3 2 1
1 2
2 3
3 4

输出 #2

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