Bob got a job as a system administrator in X corporation. His first task was to connect n servers with the help of m two-way direct connection so that it becomes possible to transmit data from one server to any other server via these connections. Each direct connection has to link two different servers, each pair of servers should have at most one direct connection. Y corporation, a business rival of X corporation, made Bob an offer that he couldn't refuse: Bob was asked to connect the servers in such a way, that when server with index v fails, the transmission of data between some other two servers becomes impossible, i.e. the system stops being connected. Help Bob connect the servers.

Input

The first input line contains 3 space-separated integer numbers n, m, v (3 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ v ≤ n), n — amount of servers, m — amount of direct connections, v — index of the server that fails and leads to the failure of the whole system.

Output

If it is impossible to connect the servers in the required way, output -1. Otherwise output m lines with 2 numbers each — description of all the direct connections in the system. Each direct connection is described by two numbers — indexes of two servers, linked by this direct connection. The servers are numbered from 1. If the answer is not unique, output any.

Examples

Input

5 6 3


Output

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


Input

6 100 1


Output

-1

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
(n, m, v) = (int(_) for _ in input().split())
if m < n - 1:
	print(-1)
elif m > (n - 1) * (n - 2) / 2 + 1:
	print(-1)
else:
	v = v % n
	print((v - 1) % n + 1, v + 1)
	for i in range(1, n - 1):
		print((v + i) % n + 1, (v + i + 1) % n + 1)
	m -= n - 1
	i = 1
	while m > 0:
		j = 2
		while m > 0 and j < n - i + 1:
			if (v + i + j) % n != v:
				print((v + i) % n + 1, (v + i + j) % n + 1)
				m -= 1
			j += 1
		i += 1


(n, m, v) = map(int, input().split())
if m < n - 1 or m > (n - 1) * (n - 2) // 2 + 1:
	print(-1)
	exit()
k = n - 1
if n == v:
	n -= 1
for i in range(1, n + 1):
	if v != i:
		print(i, ' ', v)
(x, y) = (1, 1)
while k != m:
	if x == n - 1:
		y += 1
		x = y + 1
	else:
		x += 1
	if x != v and y != v:
		print(x, ' ', y)
		k += 1


(n, m, v) = [int(i) for i in input().split()]
if m < n - 1 or m > (n - 1) * (n - 2) / 2 + 1:
	print(-1)
else:
	tmp_list = [i for i in range(1, 1 + n) if i != v]
	for i in tmp_list:
		print(v, i)
	m -= n - 1
	for i in range(n - 2):
		if m:
			for j in range(i + 1, n - 2):
				if m:
					print(tmp_list[i], tmp_list[j])
					m -= 1
				else:
					exit()


import sys
(n, m, v) = input().split(' ')
n = int(n)
m = int(m)
v = int(v)
arr = [int(x) for x in range(n + 1)]
if n - 1 > m or m > (n - 1) * (n - 2) / 2 + 1:
	print(-1)
	sys.exit()
else:
	arr[1] = v
	arr[v] = 1
for i in range(2, n + 1):
	print(arr[i], arr[1])
m = m - n + 1
for x in range(3, n + 1):
	for y in range(x + 1, n + 1):
		if m > 0:
			print(arr[x], arr[y])
			m = m - 1
		else:
			break


def print_pair(a, b):
	print(a, ' ', b)

def _print(a, b):
	for i in range(1, b + 1):
		if a != i:
			print_pair(i, a)

def main():
	(n, m, v) = map(int, input().split())
	l = (n - 1) * (n - 2)
	div = 2 + 1
	if m < n - 1 or m > l // 2 + 1:
		print(-1)
		exit()
	j = n - 1
	if n == v:
		n -= 1
	_print(v, n)
	(x, y) = (1, 1)
	while j != m:
		if x == n - 1:
			x = y + 2
			y += 1
		else:
			x += 1
		if x != v and y != v:
			print_pair(x, y)
			j += 1
main()


(servers, conn, failturePoint) = map(int, input().split(' '))

def main():
	global conn
	if conn > (servers - 1) * (servers - 2) / 2 + 1 or conn < servers - 1:
		return -1
	for i in range(1, servers + 1):
		if i != failturePoint:
			print(str(i) + ' ' + str(failturePoint))
	conn -= servers - 1
	parent = 1 if failturePoint != 1 else 2
	for i in range(1, servers + 1):
		if i != parent and i != failturePoint:
			for j in range(i + 1, servers + 1):
				if j != parent and j != failturePoint:
					if conn == 0:
						break
					else:
						print(str(i) + ' ' + str(j))
						conn -= 1
res = main()
if res == -1:
	print(res)


(nodes, connections, focal) = [int(x) for x in input().split()]
if connections > 1 + (nodes - 1) * (nodes - 2) // 2 or connections < nodes - 1:
	print(-1)
else:
	counter = 0
	dummy = 0
	for i in range(connections + 1):
		dummy += 1
		if counter <= nodes:
			if dummy != focal and dummy <= nodes:
				print(focal, dummy)
				counter += 1
		else:
			break
	if focal == nodes:
		focal = 1
	if connections > counter:
		for i in range(1, nodes):
			for j in range(i, nodes):
				if connections > counter:
					if i != focal and j != focal and (i != j):
						print(i, j)
						counter += 1
				else:
					exit()


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()]

def nCr(n, r):
	(f, m) = (factorial, 1)
	for i in range(n, n - r, -1):
		m *= i
	return int(m // f(r))
from sys import stdin
from math import factorial
(n, m, v) = arr_inp(1)
if m < n - 1 or m > nCr(n, 2):
	print(-1)
else:
	(ans, v2) = ([], n)
	if v == n:
		v2 -= 1
	for i in range(1, n + 1):
		if i != v:
			ans.append([i, v])
			m -= 1
	for i in range(1, n + 1):
		if i not in [v, v2] and m:
			for j in range(i + 1, n + 1):
				if j not in [v, v2] and m:
					ans.append([i, j])
					m -= 1
				elif m == 0:
					break
		elif m == 0:
			break
	if m:
		print(-1)
	else:
		for i in range(len(ans)):
			print(*ans[i])


(n, m, v) = map(int, input().split())
if m < n - 1 or m > (n - 1) * (n - 2) // 2 + 1:
	print(-1)
	exit()
if v == 1:
	print(1, 2)
	t = [1] + [i for i in range(3, n + 1)]
	s = 1
	(i, j) = (0, 1)
	k = len(t)
	while s < m and i < k - 1:
		print(t[i], t[j])
		j += 1
		if j == k:
			i += 1
			j = i + 1
		s += 1
else:
	print(1, v)
	t = [i for i in range(v, n + 1)] + [i for i in range(2, v)]
	s = 1
	(i, j) = (0, 1)
	k = len(t)
	while s < m and i < k - 1:
		print(t[i], t[j])
		j += 1
		if j == k:
			i += 1
			j = i + 1
		s += 1


_input = input().split()
n = int(_input[0])
m = int(_input[1])
v = int(_input[2])
issolated = v + 1 if v < n else 1
upper = (n - 1) * (n - 2) // 2 + 1
vertex = [i for i in range(1, n + 1) if i != issolated]
if m > upper or m < n - 1:
	print(-1)
else:
	connect = 1
	if m > 0:
		print(str(v) + ' ' + str(issolated))
		count = 1
		index = 0
		while count < m:
			if index + connect >= len(vertex):
				index = 0
				connect += 1
			print(str(vertex[index]) + ' ' + str(vertex[index + connect]))
			index += 1
			count += 1


import itertools
nmv = input().split()
num = int(nmv[0])
moves = int(nmv[1])
fail = int(nmv[2])
if num - 2 >= moves:
	print('-1')
elif (num - 2) * (num - 3) / 2 + num - 1 < moves:
	print('-1')
else:
	c = 1
	if fail != 1:
		k = 1
	else:
		k = 2
	a = 1
	b = 1
	for i in range(moves):
		if c == fail:
			c += 1
		if c <= num:
			print(c, fail)
			c += 1
		else:
			while a == fail or a == k:
				a += 1
			while b == fail or b == k or a >= b:
				b += 1
			if b > num:
				b = 1
				a += 1
			while a == fail or a == k:
				a += 1
			while b == fail or b == k or a >= b:
				b += 1
			print(a, b)
			b += 1


(n, m, v) = map(int, input().split())
if m < n - 1 or 2 * m > n * (n - 3) + 4:
	exit(print(-1))
r = list(range(1, n + 1))
r.pop(v - 1)
for i in r:
	print(v, i)
r.pop()
for i in r:
	for j in r:
		if j > i:
			if n > m:
				exit()
			print(i, j)
			n += 1


import sys
(ints, strs, maps, ranges, lens) = (int, str, map, range, len)
fout = []

def sumation(target):
	count = 0
	for i in range(target):
		count += target - i
	return count
(servers, connections, dead) = maps(ints, input().split())
if not (connections < servers - 1 or connections > sumation(servers - 2) + 1):
	server_list = []
	for i in ranges(servers):
		server_list.append(i + 1)
	if dead != 2:
		(server_list[1], server_list[dead - 1]) = (server_list[dead - 1], server_list[1])
	else:
		(server_list[1], server_list[0]) = (server_list[0], server_list[1])
	fout.append('{} {}'.format(server_list[0], server_list[1]))
	for i in ranges(lens(server_list[2:])):
		fout.append('{} {}'.format(server_list[1], server_list[i + 2]))
	count = connections - lens(fout)
	new_server_list = server_list[2:]
	if count > 0:
		for i in ranges(lens(new_server_list)):
			for e in ranges(i + 1, len(new_server_list)):
				fout.append('{} {}'.format(new_server_list[i], new_server_list[e]))
				count -= 1
				if count == 0:
					print('\n'.join(fout))
					sys.exit()
else:
	fout.append('-1')
print('\n'.join(fout))


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')

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, e, v) = value()
max_e = 1 + (n - 1) * (n - 2) // 2
if e > max_e or e < n - 1:
	print(-1)
else:
	if v == 1:
		set1 = 2
	else:
		set1 = 1
	print(v, set1)
	e -= 1
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if i != set1 and j != set1:
				print(i, j)
				e -= 1
			if e == 0:
				exit()


def sumOfConsecutives(x):
	return x * (x + 1) // 2
(nodes, edges, x) = [int(n) for n in input().split()]
max_edges = nodes - 1 + sumOfConsecutives(nodes - 3)
if edges > max_edges or edges < nodes - 1:
	print(-1)
else:
	for n in range(1, nodes + 1):
		if n != x:
			print(n, x)
	edges -= nodes - 1
	current_node = 1 if x != 1 else 2
	end_node = nodes if x != nodes else nodes - 1
	while edges > 0:
		for n in range(current_node + 1, end_node):
			if n != x:
				print(current_node, n)
				edges -= 1
				if edges == 0:
					break
		current_node += 1
		if current_node == x:
			current_node += 1


import sys
import math
import copy
big = set()
small = []

def main():
	input_list = get_input()
	line = [int(x) for x in input_list[0].split(' ')]
	solution = solve(line[0], line[1], line[2])
	if solution != -1:
		for i in solution:
			print(i)
	else:
		print(-1)

def get_input():
	input_list = []
	for line in sys.stdin:
		input_list.append(line.rstrip('\n'))
	return input_list

def generate_sets(n, m, v):
	global big
	global small
	if v == 1:
		small = [2, 1]
		for i in range(1, n + 1):
			big.add(i)
		big.remove(2)
		big = list(big)
	else:
		small = [1, v]
		for i in range(1, n + 1):
			big.add(i)
		big.remove(1)
		big = list(big)
	return None

def generate_basic_network(n, m, v):
	global big
	global small
	edges = set()
	temp = copy.deepcopy(big)
	temp = set(temp)
	temp.remove(v)
	temp = list(temp)
	basic = small + temp
	for i in range(len(basic) - 1):
		edges.add(str(basic[i]) + ' ' + str(basic[i + 1]))
	return edges

def solve(n, m, v):
	global big
	global small
	big = set()
	small = []
	edges = set()
	m_min = n - 1
	if m >= m_min:
		generate_sets(n, m, v)
		edges = generate_basic_network(n, m, v)
		for j in range(len(big)):
			if len(edges) == m:
				break
			for k in range(len(big[j + 1:])):
				if len(edges) == m:
					break
				edge = str(big[j]) + ' ' + str(big[j + 1:][k])
				reverse_edge = str(big[j + 1:][k]) + ' ' + str(big[j])
				if not edge in edges and (not reverse_edge in edges):
					edges.add(edge)
		if len(edges) != m:
			return -1
		return edges
	else:
		return -1
main()


(server, connect, failturePoint) = map(int, input().split(' '))

def main():
	global connect
	if connect > (server - 1) * (server - 2) / 2 + 1 or connect < server - 1:
		return -1
	for i in range(1, server + 1):
		if i != failturePoint:
			print(str(i) + ' ' + str(failturePoint))
	connect -= server - 1
	parent = 1 if failturePoint != 1 else 2
	for i in range(1, server + 1):
		if i != parent and i != failturePoint:
			for j in range(i + 1, server + 1):
				if j != parent and j != failturePoint:
					if connect == 0:
						break
					else:
						print(str(i) + ' ' + str(j))
						connect -= 1
num = main()
if num == -1:
	print(num)


import sys

def solve():
	(n, m, v) = map(int, input().split())
	if m < n - 1 or m - 1 > (n - 1) * (n - 2) // 2:
		print(-1)
		return
	additional = m - (n - 1)
	special = 1 if v != 1 else 2
	print(special, v)
	for x in range(1, n + 1):
		if x != special and x != v:
			print(v, x)
	for start in range(1, n + 1):
		for other in range(start + 1, n + 1):
			if additional == 0:
				break
			if start != special and other != special and (start != v) and (other != v):
				print(start, other)
				additional -= 1
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


import sys
from array import array

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
(n, m, v) = map(int, input().split())
if m < n - 1 or m > (n - 1) * (n - 2) // 2 + 2:
	print(-1)
	exit()

def ok(edges):
	sys.stdout.buffer.write('\n'.join(edges).encode('utf-8'))
	exit()
p = v - 1 if v > 1 else n
vs = [p, v] + [i for i in range(1, n + 1) if i != v and i != p]
edges = [f'{vs[i]} {vs[i + 1]}' for i in range(n - 1)]
m -= n - 1
if m == 0:
	ok(edges)
for i in range(1, n - 2):
	for j in range(i + 2, n):
		edges.append(f'{vs[i]} {vs[j]}')
		m -= 1
		if m == 0:
			ok(edges)
print(-1)