One day, at the "Russian Code Cup" event it was decided to play football as an out of competition event. All participants was divided into n teams and played several matches, two teams could not play against each other more than once.

The appointed Judge was the most experienced member — Pavel. But since he was the wisest of all, he soon got bored of the game and fell asleep. Waking up, he discovered that the tournament is over and the teams want to know the results of all the matches.

Pavel didn't want anyone to discover about him sleeping and not keeping an eye on the results, so he decided to recover the results of all games. To do this, he asked all the teams and learned that the real winner was friendship, that is, each team beat the other teams exactly k times. Help Pavel come up with chronology of the tournir that meets all the conditions, or otherwise report that there is no such table.


-----Input-----

The first line contains two integers — n and k (1 ≤ n, k ≤ 1000).


-----Output-----

In the first line print an integer m — number of the played games. The following m lines should contain the information about all the matches, one match per line. The i-th line should contain two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}). The numbers a_{i} and b_{i} mean, that in the i-th match the team with number a_{i} won against the team with number b_{i}. You can assume, that the teams are numbered from 1 to n.

If a tournir that meets the conditions of the problem does not exist, then print -1.


-----Examples-----
Input
3 1

Output
3
1 2
2 3
3 1

Difficulty: MEDIUM
Tags: Graph algorithms

Implementation

Constructive algorithms

Starter code:

Solutions:
(n, k) = map(int, input().split())
if n < 2 * k + 1:
	print(-1)
else:
	print(n * k)
	for i in range(1, n + 1):
		c = 1
		while c <= k:
			a = i
			b = i + c
			if i + c > n:
				a = i
				b = (i + c) % n
			print(a, b)
			c = c + 1


import sys, math
(n, k) = list(map(int, sys.stdin.readline().split()))
if n <= 2 * k:
	print(-1)
else:
	ans = []
	for i in range(n):
		for j in range(i + 1, k + i + 1):
			if j + 1 == n:
				ans.append([i + 1, j + 1])
			else:
				ans.append([i + 1, (j + 1) % n])
	print(len(ans))
	for i in range(len(ans)):
		print(*ans[i])


(n, k) = map(int, input().split(' '))
if n % 2 == 0 and k > n // 2 - 1 or (n % 2 == 1 and k > n // 2):
	print(-1)
else:
	print(n * k)
	for i in range(n):
		for j in range(k):
			if i + j + 2 > n:
				print(i + 1, i + j + 2 - n)
			else:
				print(i + 1, i + j + 2)


(n, k) = list(map(int, input().split()))
if n < 2 * k + 1:
	print(-1)
else:
	print(n * k)
	for kk in range(1, n + 1):
		for kkk in range(1, k + 1):
			if kk + kkk > n:
				print(kk, (kk + kkk) % n)
			else:
				print(kk, kk + kkk)


(n, m) = list(map(int, input().split()))
if 2 * m + 1 > n:
	print(-1)
else:
	print(n * m)
	for i in range(0, n):
		for j in range(1, m + 1):
			print(i + 1, (i + j) % n + 1)


(n, k) = map(int, input().strip().split())
if 2 * k > n - 1:
	print('-1')
else:
	r = [str(n * k)]
	for i in range(1, n + 1):
		for j in range(k):
			r.append(str(i) + ' ' + str((i + j) % n + 1))
	print('\n'.join(r))


(n, k) = [int(i) for i in input().split()]
if k > n // 2 or n < 3 or n == 2 * k:
	print(-1)
	return
print(n * k)
arr = list(range(1, n + 1)) + list(range(1, n // 2 + 1))
for i in range(arr[arr.index(max(arr))]):
	for j in range(1, k + 1):
		print(arr[i], arr[j + i])


(n, k) = map(int, input().split())
if n < 2 * k + 1:
	print(-1)
else:
	print(n * k)
	l = range(1, n + 1)
	x = n - k
	for i in range(x):
		v = l[i]
		for z in range(k):
			print(v, v + 1 + z)
	for i in range(x, n):
		v = l[i]
		for z in range(k):
			if k - (n - v) > z:
				print(v, z + 1)
			if z + 1 <= n - v:
				print(v, v + 1 + z)


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, k) = map(int, input().split())
	if n < (k << 1) + 1:
		print(-1)
		exit()
	print(n * k)
	for i in range(1, n + 1):
		j = i + 1
		z = k
		while z:
			if j == n + 1:
				j = 1
			print(i, j)
			z -= 1
			j += 1
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')
main()


(n, k) = list(map(int, input().split()))
win = [[False] * (n + 1) for _ in range(n + 1)]
count = 0
if n * (n - 1) >> 1 < n * k:
	print(-1)
else:
	for i in range(1, n + 1):
		current = k
		for j in range(1, n + 1):
			if i != j and (not win[j][i]):
				win[i][j] = True
				current -= 1
				count += 1
			if current == 0:
				break
	print(count)
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if win[i][j]:
				print(i, j)


(n, k) = input().split()
n = int(n)
k = int(k)
if n < 2 * k + 1:
	print(-1)
else:
	print(n * k)
	for i in range(1, n + 1):
		for j in range(k):
			print(i, (i + j) % n + 1)


import math
(n, k) = list(map(int, input().split()))
if k >= math.ceil(n / 2):
	print(-1)
else:
	print(n * k)
	for i in range(1, n - k + 1):
		for j in range(i + 1, i + k + 1):
			print(i, j)
	x = i + 1
	for i in range(x, n + 1):
		c = 0
		for j in range(i + 1, n + 1):
			print(i, j)
			c += 1
		j = 1
		for j in range(1, k - c + 1):
			print(i, j)
			j += 1


(n, k) = list(map(int, input().split()))
a = n * (n - 1) // 2
if n * k > a:
	print(-1)
else:
	l = set()
	for i in range(1, n + 1):
		for j in range(k):
			l.add(str(i) + ' ' + str((i + j) % n + 1))
	print(n * k)
	print('\n'.join(l))


(n, k) = tuple(map(int, input().split()))
if (n - 1) // 2 < k:
	print(-1)
else:
	answer = []
	m = n * k
	print(m)
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			a = i
			b = (i + j) % n
			if not b:
				b = n
			answer.append(str(a) + ' ' + str(b))
	print('\n'.join(answer))


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.buffer.readline())
Neo = lambda : list(map(int, sys.stdin.buffer.readline().split()))
(n, k) = Neo()
if 2 * k > n - 1:
	print(-1)
else:
	print(n * k)
	for i in range(1, n + 1):
		for j in range(i + 1, k + i + 1):
			if j > n:
				j = j % n
			print(i, j)


import sys
f = sys.stdin
(n, k) = list(map(int, f.readline().strip().split()))
if 2 * k > n - 1:
	print('-1')
else:
	r = [str(n * k)]
	for i in range(n):
		for j in range(k):
			r.append(str(i + 1) + ' ' + str((i + j + 1) % n + 1))
	print('\n'.join(r))


from sys import stdin, stdout
from collections import *
from math import ceil, floor, log, gcd
st = lambda : list(stdin.readline().strip())
li = lambda : list(map(int, stdin.readline().split()))
mp = lambda : map(int, stdin.readline().split())
inp = lambda : int(stdin.readline())
pr = lambda n: stdout.write(str(n) + '\n')
mod = 1000000007
INF = float('inf')

def solve():
	(n, k) = mp()
	x = n * (n - 1) >> 1
	if n * k > x:
		pr(-1)
		return
	ans = []
	for i in range(1, n + 1):
		for j in range(i + 1, i + k + 1):
			if j == n:
				ans.append((i, n))
			else:
				ans.append((i, j % n))
	print(len(ans))
	for i in ans:
		print(*i)
for _ in range(1):
	solve()


(n, k) = map(int, input().split())
a = n * (n - 1) // 2
if n * k > a:
	print(-1)
else:
	l = [str(n * k)]
	for i in range(1, n + 1):
		for j in range(k):
			l.append(str(i) + ' ' + str((i + j) % n + 1))
	print('\n'.join(l))


(n, k) = list(map(int, input().split()))
m = n + 1
if 2 * k > n - 1:
	print('-1')
else:
	t = []
	for i in range(1, k + 1):
		t += [str(j) + ' ' + str(j + i) for j in range(1, m - i)]
		t += [str(j) + ' ' + str(j + i - n) for j in range(m - i, m)]
	print(k * n)
	print('\n'.join(t))


from collections import deque
for _ in range(1):
	(n, k) = map(int, input().split())
	visited = set()
	ans = []
	flag = 0
	for i in range(n):
		for j in range(i + 1, i + k + 1):
			e1 = i + 1
			e2 = j % n + 1
			if (e1, e2) in visited or e1 == e2:
				flag = 1
				break
			else:
				ans.append((e1, e2))
				visited.add((e1, e2))
				visited.add((e2, e1))
		if flag:
			break
	if flag:
		print(-1)
	else:
		print(len(ans))
		for i in ans:
			print(*i)


(n, k) = map(int, input().split())
if n < 2 * k + 1:
	print(-1)
else:
	print(n * k)
	for i in range(1, n + 1):
		for z in range(k):
			print(i, (i + z) % n + 1)


(n, k) = map(int, input().split())
s = []
if k >= n / 2:
	print(-1)
else:
	print(n * k)
	for i in range(n):
		for j in range(k):
			a = i + 1
			b = i + j + 2 if i + j + 2 <= n else i + j + 2 - n
			s.append('%d %d' % (a, b))
	print('\n'.join(s))


(n, k) = map(int, input().split())
if k > (n - 1) // 2:
	print(-1)
else:
	print(n * k)
	for i in range(n):
		for j in range(k):
			l = i
			r = l + j + 1
			print(l + 1, r % n + 1)


def pair(a, b):
	if a > b:
		return pair(b, a)
	else:
		return (a + b) * (a + b + 1) / 2 + b
(n, k) = list(map(int, input().split()))
if k > int((n - 1) / 2):
	print('-1')
else:
	print(n * k)
	hash = {}
	for i in range(1, n + 1):
		j = 1
		count = 0
		while j <= n and count < k:
			if i == j:
				j += 1
				continue
			else:
				p = pair(i, j)
				if p in hash:
					j += 1
					continue
				else:
					hash[p] = 1
					print('%d %d' % (i, j))
					count += 1
					j += 1


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
(n, k) = (int(i) for i in input().split())
if n * k > n * (n - 1) // 2:
	print(-1)
else:
	print(n * k)
	for i in range(1, n + 1):
		c = 0
		if i == n:
			j = 1
		else:
			j = i + 1
		while c < k:
			print(i, j)
			if j == n:
				j = 1
			else:
				j += 1
			c += 1


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(n, k) = ilele()
if not 2 * k <= n - 1:
	print(-1)
else:
	print(n * k)
	for i in range(1, n + 1):
		for j in range(i + 1, i + 1 + k):
			if j > n:
				j = j - n
			print(i, j)