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.

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.

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 $\frac{m(m - 1)}{2}$ (at most $\frac{m(m - 1)}{2}$ pairs). Help Iahub, find any suitable array.


-----Input-----

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 ≤ 10^6 holds.


-----Output-----

On the first line of the output print an integer p, the size of the array (p can be at most $\frac{m(m - 1)}{2}$). Each of the next p lines must contain two distinct integers i and j (1 ≤ i, j ≤ m, i ≠ j), representing the chosen indices.

If there are multiple correct answers, you can print any.


-----Examples-----
Input
2 5 0
1 3 2 5 4
1 4 3 2 5

Output
3
2 4
2 3
4 5

Input
3 2 1
1 2
2 3
3 4

Output
1
2 1



-----Note-----

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

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms


Solutions:
def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return [str(x) for x in stdin.readline().split()]
from sys import stdin
from itertools import *
(n, m, k) = arr_inp(1)
(arr, ans) = ([arr_inp(1) for i in range(n)], list(combinations(list(range(1, m + 1)), 2)))
print(len(ans))
for i in range(len(ans)):
	if k:
		print(ans[i][1], ans[i][0])
	else:
		print(ans[i][0], ans[i][1])


(_, m, k) = map(int, input().split())
print(m * (m - 1) // 2)
for i in range(m):
	for j in range(i + 1, m):
		print(j + 1, i + 1) if k else print(i + 1, j + 1)


from sys import stdin, stdout
import math
from collections import Counter, deque
L = lambda : list(map(int, stdin.readline().strip().split()))
M = lambda : map(int, stdin.readline().strip().split())
I = lambda : int(stdin.readline().strip())
IN = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()
mod = 1000000007

def s(a):
	print(' '.join(list(map(str, a))))

def solve():
	(n, m, k) = M()
	print(m * (m - 1) // 2)
	for i in range(1, m + 1):
		for j in range(i + 1, m + 1):
			if k:
				print(j, i)
			else:
				print(i, j)
for i in range(1):
	solve()


(n, m, k) = map(int, input().split())
print(m * (m - 1) // 2)
for i in range(m - 1):
	for j in range(m - 1 - i):
		print('{} {}'.format(*((j + 1, j + 2) if k == 0 else (j + 2, j + 1))))


import sys
inf = float('inf')
mod = 1000000007

def array():
	return list(map(int, sys.stdin.readline().split()))

def intt():
	return map(int, sys.stdin.readline().split())
from bisect import bisect_left
import sys
(n, m, k) = map(int, sys.stdin.readline().split())
ls = []
for i in range(n):
	arr = list(map(int, sys.stdin.readline().split()))
	ls.append(arr)
print(m * (m - 1) // 2)
for i in range(1, m):
	for j in range(i + 1, m + 1):
		if k == 0:
			print(i, j)
		else:
			print(j, i)


from collections import *
from math import *
(n, m, k) = list(map(int, input().split()))
a = []
if k == 0:
	for i in range(m):
		for j in range(i + 1, m):
			a.append([i + 1, j + 1])
else:
	for i in range(m - 1, -1, -1):
		for j in range(i - 1, -1, -1):
			a.append([i + 1, j + 1])
print(len(a))
for i in a:
	print(*i)


def main():
	(n, m, k) = map(int, input().split())
	print(m * (m - 1) // 2)
	for i in range(1, m):
		for j in range(i + 1, m + 1):
			print(j, i) if k else print(i, j)

def __starting_point():
	main()
__starting_point()


(n, m, k) = map(int, input().split())
arrays = []
for i in range(n):
	arrays.append(list(map(int, input().split())))
print(m * (m - 1) // 2)
if k == 0:
	for i in range(1, m):
		for j in range(1, m - i + 1):
			print(j, j + 1)
else:
	for i in range(1, m):
		for j in range(m, i, -1):
			print(j, j - 1)


(n, m, k) = map(int, input().split())
for i in range(n):
	a = [int(x) for x in input().split()]
d = []
for i in range(1, m):
	for j in range(i + 1, m + 1):
		if k == 0:
			d.append((i, j))
		else:
			d.append((j, i))
print(len(d))
for i in d:
	print(*i)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 1000000007

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, m, o) = value()
for i in range(n):
	input()
print(m * (m - 1) // 2)
for i in range(1, m + 1):
	for j in range(i + 1, m + 1):
		if o == 0:
			print(i, j)
		else:
			print(m - i + 1, m - j + 1)


(n, m, k) = list(map(int, input().split()))
for i in range(n):
	li = list(map(int, input().split()))
ans = []
for i in range(1, m + 1):
	for j in range(i + 1, m + 1):
		ans.append([i, j])
if k == 0:
	print(len(ans))
	for i in ans:
		print(*i)
else:
	print(len(ans))
	for i in ans[::-1]:
		print(*i[::-1])


from collections import *
import sys
input = sys.stdin.readline

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
(n, m, k) = rl()
AA = []
for _ in range(n):
	AA.append(rl())
print(m * (m - 1) // 2)
if k == 0:
	for i in range(1, m + 1):
		for j in range(i + 1, m + 1):
			print(i, j)
else:
	for i in range(1, m + 1):
		for j in range(i + 1, m + 1):
			print(j, i)


(n, m, k) = list(map(int, input().split()))
for i in range(n):
	a = list(map(int, input().split()))
if k == 0:
	x = 1
	y = m + 1
	z = 1
else:
	x = m
	y = 0
	z = -1
print(m * (m - 1) // 2)
for i in range(x, y, z):
	for j in range(x, y, z):
		if k == 0 and i < j:
			print(i, j)
		if k == 1 and i > j:
			print(i, j)