Let's call an undirected graph $G = (V, E)$ relatively prime if and only if for each edge $(v, u) \in E$  $GCD(v, u) = 1$ (the greatest common divisor of $v$ and $u$ is $1$). If there is no edge between some pair of vertices $v$ and $u$ then the value of $GCD(v, u)$ doesn't matter. The vertices are numbered from $1$ to $|V|$.

Construct a relatively prime graph with $n$ vertices and $m$ edges such that it is connected and it contains neither self-loops nor multiple edges.

If there exists no valid graph with the given number of vertices and edges then output "Impossible".

If there are multiple answers then print any of them.


-----Input-----

The only line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of vertices and the number of edges.


-----Output-----

If there exists no valid graph with the given number of vertices and edges then output "Impossible".

Otherwise print the answer in the following format:

The first line should contain the word "Possible".

The $i$-th of the next $m$ lines should contain the $i$-th edge $(v_i, u_i)$ of the resulting graph ($1 \le v_i, u_i \le n, v_i \neq u_i$). For each pair $(v, u)$ there can be no more pairs $(v, u)$ or $(u, v)$. The vertices are numbered from $1$ to $n$.

If there are multiple answers then print any of them.


-----Examples-----
Input
5 6

Output
Possible
2 5
3 2
5 1
3 4
4 1
5 4

Input
6 12

Output
Impossible



-----Note-----

Here is the representation of the graph from the first example: [Image]

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms

Greedy algorithms

Complete search

Mathematics
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
from math import gcd
(n, m) = list(map(int, input().split()))
edges = []
p = m
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			m -= 1
			edges.append([i, j])
			if m == 0:
				break
	if m == 0:
		break
if len(edges) >= p and p >= n - 1:
	print('Possible')
	for i in range(len(edges)):
		print(*edges[i])
else:
	print('Impossible')


def gcd(a, b):
	c = 0
	while b > 0:
		c = a % b
		a = b
		b = c
	return a
arr = list(map(int, input().split()))
n = arr[0]
m = arr[1]
if m < n - 1:
	print('Impossible')
	exit()
vec = []
for i in range(n):
	for j in range(i + 1, n):
		if gcd(int(i + 1), int(j + 1)) == 1:
			m -= 1
			vec.append({i + 1, j + 1})
		if m == 0:
			break
	if m == 0:
		break
if m > 0:
	print('Impossible')
	exit()
print('Possible')
for (x, y) in vec:
	print('%d %d' % (x, y))


from math import *
(n, m) = list(map(int, input().split()))
if m < n - 1:
	print('Impossible')
	return
r = [(i + 1, i + 2) for i in range(n - 1)]
k = n - 1
if k >= m:
	print('Possible')
	for x in r:
		print(*x)
	return
for i in range(1, n + 1):
	for j in range(i + 2, n + 1):
		if gcd(i, j) == 1:
			r.append((i, j))
			k += 1
		if k >= m:
			print('Possible')
			for x in r:
				print(*x)
			return
print('Impossible')


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq

def check_prime(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
ba = []
for i in range(2, 10 ** 5):
	if check_prime(i):
		ba.append(i)
		if len(ba) == 1000:
			break
(n, m) = map(int, input().split())
hash = defaultdict(set)
cnt = n - 1
for i in range(1, n):
	hash[i].add(i + 1)
for i in range(3, n + 1):
	hash[1].add(i)
	cnt += 1
if n <= 2500:
	for i in range(2, n + 1):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				if j not in hash[i]:
					hash[i].add(j)
					cnt += 1
	ha = 0
	seti = set()
	ans = []
	if cnt >= m:
		for z in hash:
			for k in hash[z]:
				ans.append((z, k))
				ha += 1
				seti.add(z)
				seti.add(k)
				if ha == m:
					if len(seti) == n:
						break
					else:
						print('Impossible')
						exit()
			if ha == m:
				break
		print('Possible')
		for i in ans:
			print(*i)
	else:
		print('Impossible')
else:
	for i in range(len(ba)):
		for j in range(i + 1, len(ba)):
			if ba[j] not in hash[ba[i]] and ba[j] <= n and (ba[i] <= n):
				hash[ba[i]].add(ba[j])
				cnt += 1
	ha = 0
	seti = set()
	ans = []
	if cnt >= m:
		for z in hash:
			for k in hash[z]:
				ans.append((z, k))
				ha += 1
				seti.add(z)
				seti.add(k)
				if ha == m:
					if len(seti) == n:
						break
					else:
						print('Impossible')
						exit()
			if ha == m:
				break
		print('Possible')
		for i in ans:
			print(*i)
	else:
		print('Impossible')


from math import gcd
(n, m) = map(int, input().split())
l = []
cnt = 0
if n >= m + 2:
	print('Impossible')
else:
	for i in range(1, n):
		l.append([i, i + 1])
		cnt = cnt + 1
		if cnt == m:
			break
	for i in range(1, n + 1):
		if cnt == m:
			break
		for j in range(i + 2, n + 1):
			if gcd(i, j) == 1:
				l.append([i, j])
				cnt = cnt + 1
			if cnt == m:
				break
	if cnt < m:
		print('Impossible')
	else:
		print('Possible')
		for i in l:
			print(i[0], end=' ')
			print(i[1])


from math import gcd
(n, m) = list(map(int, input().split()))
arr = []
prime = [True for i in range(n + 1)]
for i in range(2, len(prime)):
	if prime[i] == True:
		for j in range(i * i, len(prime), i):
			prime[j] = False
for i in range(2, len(prime)):
	if prime[i]:
		arr.append(i)
cnt = m
edges = []
arr = [1] + arr
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if j > i and i != j and (gcd(i, j) == 1):
			edges.append([i, j])
			cnt -= 1
			if cnt == 0:
				break
	if cnt == 0:
		break
if len(edges) >= m and m >= n - 1:
	print('Possible')
	for i in range(len(edges)):
		print(*edges[i])
else:
	print('Impossible')


from math import gcd
(n, m) = map(int, input().split())
count = 0
ans = []
if m < n - 1:
	print('Impossible')
	exit(0)
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if count == m:
			break
		if gcd(i, j) == 1:
			count += 1
			ans.append((i, j))
if not count == m:
	print('Impossible')
	exit(0)
print('Possible')
for (i, j) in ans:
	print(i, j)


from math import gcd
(n, m) = map(int, input().split())
sol = []
total = 0
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			sol.append((i, j))
			total += 1
		if total >= m:
			break
	if total >= m:
		break
if total >= m and m >= n - 1:
	print('Possible')
	print('\n'.join((str(x) + ' ' + str(y) for (x, y) in sol)))
else:
	print('Impossible')


import math
p = list(map(int, input().split()))
n = p[0]
m = p[1]
ans1 = []
ans2 = []
sum = int(n - 1)
tot = int(0)
if sum > m:
	print('Impossible')
else:
	for i in range(2, n + 1):
		ans1.append(1)
		ans2.append(i)
		tot += 1
		m -= 1
	for i in range(2, n):
		for j in range(i + 1, n + 1):
			if m == 0:
				break
			ff = int(math.gcd(i, j))
			if ff == 1:
				ans1.append(i)
				ans2.append(j)
				tot += 1
				m -= 1
	if m > 0:
		print('Impossible')
	else:
		print('Possible')
		for i in range(0, tot):
			print(ans1[i], end=' ')
			print(ans2[i])


from fractions import gcd
import sys
(n, m) = list(map(int, input().split()))
if m < n - 1:
	print('Impossible')
	sys.exit(0)
fnd = 0
res = ''
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			fnd += 1
			res += '%d %d\n' % (i, j)
			if fnd == m:
				print('Possible')
				print(res)
				sys.exit(0)
print('Impossible')


from math import gcd
(n, m) = map(int, input().split())
a = list()
if m < n - 1:
	print('Impossible')
	exit()
a = [[] for i in range(m)]
cur = 0
for i in range(1, n):
	a[cur] = [i, i + 1]
	cur += 1
if cur == m:
	print('Possible')
	for v in a:
		print(v[0], v[1], sep=' ')
	exit()
for i in range(1, n):
	for j in range(i + 2, n + 1):
		if gcd(i, j) == 1:
			a[cur] = [i, j]
			cur += 1
		if cur == m:
			print('Possible')
			for v in a:
				print(v[0], v[1], sep=' ')
			exit()
print('Impossible')


def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)
(n, m) = list(map(int, input().split()))
b = []
c = 0
e = 0
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			b.append([i, j])
			c = c + 1
		if c == m:
			e = 1
			break
	if e == 1:
		break
if e == 1 and m >= n - 1:
	print('Possible')
	for i in range(m):
		print(*b[i])
else:
	print('Impossible')


from math import gcd as bltin_gcd

def cp(a, b):
	return bltin_gcd(a, b) == 1
(n, m) = [int(x) for x in input().split()]
ans = []
yes = 'Possible'
no = 'Impossible'

def pri():
	print(yes)
	for x in ans:
		print(x[0], ' ', x[1])
if m < n - 1:
	print(no)
	quit()
if m == n - 1:
	print(yes)
	for i in range(1, m + 1):
		print(i, ' ', i + 1)
	quit()
for i in range(1, n):
	ans.append((i, i % n + 1))
for i in range(1, n + 1):
	for j in range(i + 2, n + 1):
		if i % 2 == 0 and j % 2 == 0:
			continue
		if cp(i, j):
			ans.append((i, j))
			if len(ans) == m:
				pri()
				quit()
print(no)


import math
(n, m) = map(int, input().split())
if m < n - 1:
	print('Impossible')
else:
	c = 0
	flag = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if math.gcd(i, j) == 1:
				c += 1
			if c >= m:
				flag = 1
				break
		if flag == 1:
			break
	if flag == 0:
		print('Impossible')
	else:
		print('Possible')
		c = 0
		flag = 0
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if math.gcd(i, j) == 1:
					print(i, j)
					c += 1
				if c >= m:
					flag = 1
					break
			if flag == 1:
				break


from itertools import islice

def get_all(n):
	q = [(0, 1, 1, 1)]
	while q:
		(a, b, c, d) = q.pop()
		(e, f) = (a + c, b + d)
		if f <= n:
			yield (e, f)
			q.append((a, b, e, f))
			q.append((e, f, c, d))

def solve(n, m):
	x = list(islice(get_all(n), m))
	if len(x) == m >= n - 1:
		return x
res = solve(*map(int, input().split()))
if res is not None:
	print('Possible')
	for e in res:
		print(*e)
else:
	print('Impossible')


def gcd(n1, n2):
	if n2 > n1:
		return gcd(n2, n1)
	if n2 == 0:
		return n1
	return gcd(n2, n1 % n2)

def main():
	(n, m) = map(int, input().split())
	if m < n - 1:
		print('Impossible')
		return
	ans = []
	for i in range(1, n):
		j = 2
		curr = set()
		while i * j <= n:
			curr.add(i * j)
			j += 1
		if i == 1:
			for j in curr:
				ans.append((i, j))
				if len(ans) == m:
					break
		else:
			for j in range(i + 1, n + 1):
				if j not in curr and gcd(i, j) == 1:
					ans.append((i, j))
					if len(ans) == m:
						break
		if len(ans) == m:
			break
	if len(ans) != m:
		print('Impossible')
		return
	print('Possible')
	for i in ans:
		print(i[0], i[1])
main()


import math
(n, m) = map(int, input().split())
if m < n - 1:
	print('Impossible')
else:
	ans = []
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if math.gcd(i, j) == 1:
				ans.append([i, j])
				m -= 1
				if m == 0:
					break
		if m == 0:
			break
	if m != 0:
		print('Impossible')
	else:
		print('Possible')
		for i in range(0, len(ans)):
			res = ''
			for j in range(2):
				res += str(ans[i][j]) + ' '
			print(res)


[n, m] = [int(i) for i in input().split()]
gcd = lambda x, y: x if not y else gcd(y, x % y)
if m < n - 1:
	print('Impossible')
else:
	pairs = []
	flag = 0
	i = 0
	while i < n and (not flag):
		j = i + 1
		while j < n and (not flag):
			if len(pairs) == m:
				flag = 1
			elif gcd(i + 1, j + 1) == 1:
				pairs.append((i + 1, j + 1))
			j += 1
		i += 1
	if len(pairs) != m:
		print('Impossible')
	else:
		print('Possible')
		for p in pairs:
			print(p[0], p[1])


import math
(n, m) = map(int, input().split(' '))
z = []
a = 1
b = 2
tot = 0
while tot < m:
	if math.gcd(a, b) == 1:
		z.append([a, b])
		tot += 1
	b += 1
	if b > n:
		a += 1
		b = a + 1
	if a >= n:
		break
if len(z) == m and n != 1 and (m >= n - 1):
	print('Possible')
	for i in range(m):
		print(str(z[i][0]) + ' ' + str(z[i][1]))
else:
	print('Impossible')


def make_prime_factors(n: int) -> list:
	prime_factors = []
	for k in range(2, int(n ** 0.5) + 1):
		while n % k == 0:
			prime_factors.append(k)
			n = n // k
	if n != 1:
		prime_factors.append(n)
	return set(prime_factors)
import sys
input = sys.stdin.readline

def solve(n, m):
	ans = []
	for num in range(1, n + 1):
		set_ = make_prime_factors(num)
		for i in range(num + 1, n + 1):
			for div in set_:
				if i % div == 0:
					break
			else:
				ans.append((i, num))
				m -= 1
				if m == 0:
					return ans
	print('Impossible')
	exit()
(n, m) = map(int, input().split())
if n - 1 > m:
	print('Impossible')
	exit()
ans = solve(n, m)
print('Possible')
for i in ans:
	print(*i)


import math
(n, m) = map(int, input().split(' '))

def sigma(n):
	count = 0
	for i in range(1, n):
		if math.gcd(i, n) == 1:
			count += 1
	return count
max_edges = 0
for i in range(2, n + 1):
	max_edges += sigma(i)
	if max_edges > 10 ** 5:
		break
if m < n - 1 or m > max_edges:
	print('Impossible')
else:
	print('Possible')
	for i in range(2, n + 1):
		print(1, i)
	edges_left = m - n + 1
	curr_vert = 3
	connect_to = 2
	while edges_left > 0:
		if math.gcd(connect_to, curr_vert) == 1:
			print(connect_to, curr_vert)
			edges_left -= 1
		if connect_to + 1 < curr_vert:
			connect_to += 1
		else:
			curr_vert += 1
			connect_to = 2


import math
(n, m) = [int(x) for x in input().split()]
if m < n - 1:
	print('Impossible')
else:
	count = 0
	flag = False
	ans = list()
	for i in range(1, n):
		if flag:
			break
		for j in range(i + 1, n + 1):
			if count == m:
				flag = True
				break
			if math.gcd(i, j) == 1:
				count += 1
				ans.append([i, j])
	if count < m:
		print('Impossible')
	else:
		print('Possible')
		for x in ans:
			print(x[0], x[1])


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
nm = input().split()
n = int(nm[0])
m = int(nm[1])
if m < n - 1:
	print('Impossible')
else:
	l = []
	cnt = 0
	f = 0
	for i in range(1, n):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				l.append((i, j))
				cnt += 1
				if cnt == m:
					f = 1
					break
		if f == 1:
			break
	if f == 0:
		print('Impossible')
	else:
		print('Possible')
		for x in l:
			print(*x)


import time
from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter

def read():
	return int(input())

def readmap():
	return map(int, input().split())

def readlist():
	return list(map(int, input().split()))

def make_relatively_prime_list(n, m):
	tree = []
	for i in range(2, n + 1):
		tree.append((i, 1))
	cnt = n - 1
	new_leaf = [(2, 1)]
	while cnt < m:
		leaf = deepcopy(new_leaf)
		new_leaf = []
		if not leaf:
			break
		for (x, y) in leaf:
			if max(2 * x - y, x) <= n:
				new_leaf.append((2 * x - y, x))
				if x > 1:
					tree.append((2 * x - y, x))
					cnt += 1
			if cnt < m and max(2 * x + y, x) <= n:
				new_leaf.append((2 * x + y, x))
				if x > 1:
					tree.append((2 * x + y, x))
					cnt += 1
			if cnt < m and max(x + 2 * y, y) <= n:
				new_leaf.append((x + 2 * y, y))
				if y > 1:
					tree.append((x + 2 * y, y))
					cnt += 1
	if n == 2:
		return tree
	new_leaf = [(3, 1)]
	while cnt < m:
		leaf = deepcopy(new_leaf)
		new_leaf = []
		if not leaf:
			break
		for (x, y) in leaf:
			if max(2 * x - y, x) <= n:
				new_leaf.append((2 * x - y, x))
				if x > 1:
					tree.append((2 * x - y, x))
					cnt += 1
			if cnt < m and max(2 * x + y, x) <= n:
				new_leaf.append((2 * x + y, x))
				if x > 1:
					tree.append((2 * x + y, x))
					cnt += 1
			if cnt < m and max(x + 2 * y, y) <= n:
				new_leaf.append((x + 2 * y, y))
				if y > 1:
					tree.append((x + 2 * y, y))
					cnt += 1
	return tree
(n, m) = readmap()
if n == 1 or m < n - 1:
	print('Impossible')
	quit()
tree = make_relatively_prime_list(n, m)
if len(tree) < m:
	print('Impossible')
else:
	print('Possible')
	for i in range(m):
		print(tree[i][0], tree[i][1])


import math

def no():
	print('Impossible')
	exit(0)
(n, m) = map(int, input().split())
if m < n - 1:
	no()
ed = [(1, i) for i in range(2, n + 1)]
now = 2
while len(ed) < m and now <= n:
	nxt = now + 1
	while nxt <= n and len(ed) < m:
		if math.gcd(now, nxt) == 1:
			ed.append((now, nxt))
		nxt += 1
	now += 1
if len(ed) < m:
	no()
print('Possible')
for e in ed:
	print(*e)


from math import gcd
(n, m) = map(int, input().split())
a = []
if m < n - 1:
	print('Impossible')
	exit()
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			a.append([i, j])
		if len(a) == m:
			break
	if len(a) == m:
		break
if len(a) != m:
	print('Impossible')
	exit()
print('Possible')
for x in a:
	print(x[0], x[1])


from fractions import gcd
(n, m) = list(map(lambda x: int(x), input().split()))
cnt = 0
pairs = []
if m < n - 1:
	print('Impossible')
	exit(0)
for i in range(1, n + 1):
	for j in range(i, n + 1):
		if i == j:
			continue
		if gcd(i, j) == 1:
			cnt += 1
			pairs.append((i, j))
		if cnt == m:
			print('Possible')
			for (f, s) in pairs[:m]:
				print('{:d} {:d}'.format(f, s))
			exit(0)
print('Impossible')


def gcd(a, b):
	while b != 0:
		t = a
		a = b
		b = t % b
	return a
(n, m) = map(int, input().split())
c = 0
ans = 'Possible ' + chr(10)
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			ans += str(i) + ' ' + str(j) + chr(10)
			c += 1
		if c == m:
			break
	if c == m:
		break
if c != m or n - 1 > m:
	print('Impossible')
else:
	print(ans)


import math
(n, m) = map(int, input().split())
if m > n * (n - 1) // 2 or m < n - 1:
	print('Impossible')
	return
rm = m - (n - 1)
ans = [(0, 0)] * (rm * 10)
f = 0
for i in range(3, n + 1):
	for j in range(1, i - 1):
		if not rm:
			break
		if math.gcd(j, i) == 1:
			ans[f] = (j, i)
			f += 1
			rm -= 1
if rm:
	print('Impossible')
	return
print('Possible')
for i in range(1, n):
	print(i, i + 1)
for i in range(f):
	print(ans[i][0], ans[i][1])


from math import gcd
(n, m) = map(int, input().split())
edges = []
cnt = 0
if m < n - 1:
	print('Impossible')
else:
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				edges.append((i, j))
				cnt += 1
				if cnt == m:
					break
		if cnt == m:
			break
	if cnt != m:
		print('Impossible')
	else:
		print('Possible')
		for pair in edges:
			print(*pair)


import math
string_input = input()
P = string_input.split()
(n, m) = [int(a) for a in P]
if m < n - 1 or m > n * (n - 1) / 2:
	print('Impossible')
else:
	records = []
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if math.gcd(i, j) == 1:
				records.append((i, j))
				if len(records) == m:
					print('Possible')
					for pair in records:
						print(pair[0], pair[1])
					exit(0)
	print('Impossible')


def gcd_recursive(a, b):
	if b == 0:
		return a
	else:
		return gcd_recursive(b, a % b)
out = []
inp = [int(x) for x in input().split(' ')]
if inp[1] < inp[0] - 1:
	print('Impossible')
else:
	for a in range(1, inp[0]):
		if len(out) == inp[1] - inp[0] + 1:
			print('Possible')
			for i in range(inp[0] - 1):
				print(1, i + 2)
			for elem in out:
				print(elem[0], elem[1])
			break
		for b in range(a + 1, inp[0]):
			gcd = gcd_recursive(a + 1, b + 1)
			if gcd == 1:
				out.append((a + 1, b + 1))
			if len(out) == inp[1] - inp[0] + 1:
				break
	else:
		print('Impossible')


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
(n, m) = [int(i) for i in input().split()]
mi = n - 1
mx = n * (n - 1) // 2
if m < mi:
	print('Impossible')
else:
	l = []
	c = 0
	for i in range(1, n):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				l.append([i, j])
				c += 1
			if c == m:
				break
		if c == m:
			break
	if c == m:
		print('Possible')
		for i in l:
			print(*i)
	else:
		print('Impossible')


def gcd(a, b):
	return b if a % b == 0 else gcd(b, a % b)
(n, m) = [int(x) for x in input().split()]
if m < n - 1:
	print('Impossible')
elif m == n - 1:
	print('Possible')
	for i in range(1, n):
		print(i, i + 1)
else:
	ct = 0
	pairs = []
	done = False
	for i in range(1, n):
		if done:
			break
		for j in range(i + 1, n + 1):
			if ct == m:
				done = True
				break
			if i == 1:
				pairs += [(i, j)]
				ct += 1
			elif gcd(i, j) == 1:
				pairs += [(i, j)]
				ct += 1
	if len(pairs) < m:
		print('Impossible')
	else:
		print('Possible')
		for (i, j) in pairs:
			print(i, j)


def gcd(a, b):
	return a if not b else gcd(b, a % b)
(n, m) = map(int, input().split())
(ans, cnt) = ('Possible', 0)
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			cnt += 1
			ans += '\n%d %d' % (i, j)
			if cnt == m:
				break
	if cnt == m:
		break
print(ans if cnt == m and m > n - 2 else 'Impossible')


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
(n, m) = map(int, input().split())
if n - 1 > m:
	exit(print('Impossible'))
ans = []
co = m
for i in range(1, n):
	ans.append((i, i + 1))
	co -= 1
for i in range(1, n + 1):
	for j in range(i + 2, n + 1):
		if co == 0:
			break
		if gcd(i, j) == 1:
			ans.append((i, j))
			co -= 1
if co == 0:
	print('Possible')
	for i in range(m):
		print(*ans[i])
else:
	print('Impossible')


import sys
import math
(n, m) = map(int, input().split())
if m < n - 1:
	print('Impossible')
	sys.exit()
l = []
for i in range(1, n):
	l.append((i, i + 1))
m -= n - 1
for i in range(1, n + 1):
	if m == 0:
		break
	for j in range(i + 2, n + 1):
		if math.gcd(i, j) == 1:
			l.append((i, j))
			m -= 1
		if m == 0:
			break
if m == 0:
	print('Possible')
	for (a, b) in l:
		print(a, b)
else:
	print('Impossible')


from math import *
(n, m) = [int(e) for e in input().split(' ')]
if m + 1 < n:
	print('Impossible')
	exit()
ans = []
len = 0
for k in range(1, n + 1):
	for j in range(k + 1, n + 1):
		if gcd(j, k) == 1:
			len += 1
			ans.append(str(k) + ' ' + str(j))
			if len == m:
				print('Possible')
				print('\n'.join(ans))
				exit()
print('Impossible')


import math
(n, m) = map(int, input().split())
if m < n - 1:
	print('Impossible')
else:
	c = 0
	d = []
	for i in range(1, n + 1):
		for k in [f for f in range(i + 1, n + 1) if math.gcd(f, i) == 1]:
			d.append(str(i) + ' ' + str(k))
			c += 1
			if c == m:
				print('Possible')
				for e in d:
					print(e)
				break
		else:
			continue
		break
	else:
		print('Impossible')


from math import gcd

def impossible():
	print('Impossible')

def possible(res):
	print(f'Possible\n{res}')

def solve(n, m):
	if m < n - 1:
		impossible()
		return
	res = ''
	for i in range(2, n + 1):
		res += f'1 {i}\n'
	m -= n - 1
	for i in range(2, n + 1):
		for j in range(i + 1, n + 1):
			if m == 0:
				possible(res)
				return
			elif gcd(i, j) == 1:
				res += f'{i} {j}\n'
				m -= 1
	if m != 0:
		impossible()
	else:
		possible(res)
(n, m) = [int(x) for x in input().split(' ')]
solve(n, m)


import collections
from functools import cmp_to_key
import math
import sys

def getIntList():
	return list(map(int, input().split()))
import bisect
try:
	import numpy
	dprint = print
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass

def makePair(z):
	return [(z[i], z[i + 1]) for i in range(0, len(z), 2)]

def memo(func):
	cache = {}

	def wrap(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return wrap

@memo
def comb(n, k):
	if k == 0:
		return 1
	if n == k:
		return 1
	return comb(n - 1, k - 1) + comb(n - 1, k)
from fractions import gcd
(n, m) = getIntList()
if m + 1 < n:
	print('Impossible')
	sys.exit()
res = 0
zz = []

def outres():
	print('Possible')
	for x in zz:
		print(x[0], x[1])
	sys.exit()
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			res += 1
			zz.append((i, j))
			if res == m:
				outres()
print('Impossible')


from copy import deepcopy
nm = list(map(int, input(' ').split(' ')))
n = nm[0]
m = nm[1]
max = 0
min = n - 1
ans = []

def euler(a):
	result = deepcopy(a)
	i = 2
	while i * i <= a:
		if a % i == 0:
			while a % i == 0:
				a /= i
			result -= result / i
		i += 1
	if a > 1:
		result -= result / a
	return int(result)

def euclid(a, b):
	if b > 0:
		return euclid(b, a % b)
	else:
		return a
if m < n - 1:
	print('Impossible')
	exit()
for i in range(n - 1):
	ans.append([i + 2, 1])
if n < 600:
	for i in range(2, n + 1):
		max += euler(i)
for i in range(2, n + 1):
	for j in range(i, 1, -1):
		if euclid(i, j) == 1:
			ans.append([i, j])
		if len(ans) == m:
			break
	if len(ans) == m:
		break
if m > max and n < 600:
	print('Impossible')
	exit()
print('Possible')
for i in range(len(ans)):
	for j in range(2):
		print(ans[i][j], ' ', end='')
	print()


import math

def solve(N, M):
	if M < N - 1:
		return None
	edges = []
	for i in range(2, N + 1):
		edges.append((1, i))
	for u in range(2, N + 1):
		if len(edges) == M:
			break
		for v in range(u + 1, N + 1):
			if len(edges) == M:
				break
			if math.gcd(u, v) == 1:
				edges.append((u, v))
	if len(edges) < M:
		return None
	return edges

def main():
	(N, M) = [int(e) for e in input().split(' ')]
	edges = solve(N, M)
	if edges is None:
		print('Impossible')
		return
	print('Possible')
	for (u, v) in edges:
		print(u, v)
main()


import math
(n, m) = map(int, input().split())
a = []
for i in range(1, n + 1):
	j = i + 1
	while len(a) < m and j <= n:
		if math.gcd(i, j) == 1:
			a.append([i, j])
		j += 1
if len(a) != m or m < n - 1:
	print('Impossible')
else:
	print('Possible')
	for i in a:
		print(i[0], i[1])


from math import gcd
(n, m) = [int(x) for x in input().strip().split()]
if n - 1 > m:
	print('Impossible')
	exit()
edges = []
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			edges.append([i, j])
			if len(edges) == m:
				print('Possible')
				for edge in edges:
					print(*edge)
				exit()
print('Impossible')


TN = 1

def solution():
	from fractions import gcd
	(n, m) = map(int, input().split())
	a = []
	for i in range(1, n):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				a.append([i, j])
			if len(a) == m:
				break
		if len(a) == m:
			break
	if m < n - 1 or len(a) != m:
		print('Impossible')
	else:
		print('Possible')
		for x in a:
			print(x[0], x[1])
while TN != 0:
	solution()
	TN -= 1


import functools
import time

def timer(func):

	@functools.wraps(func)
	def wrapper(*args, **kwargs):
		stime = time.perf_counter()
		res = func(*args, **kwargs)
		elapsed = time.perf_counter() - stime
		print(f'{func.__name__} in {elapsed:.4f} secs')
		return res
	return wrapper

class solver:

	def __init__(self):
		pass

	def __call__(self):
		(n, m) = map(int, input().strip().split())

		def gcd(a, b):
			if a < b:
				(a, b) = (b, a)
			return a if b == 0 else gcd(b, a % b)
		edges = list()
		u = 1
		cnt = 0
		while u < n:
			for v in range(u + 1, n + 1):
				if u == 1:
					edges.append((u, v))
					cnt += 1
					if cnt >= m:
						break
				elif gcd(u, v) == 1:
					edges.append((u, v))
					cnt += 1
					if cnt >= m:
						break
			if cnt >= m:
				break
			u += 1
		if cnt < m or m + 1 < n:
			print('Impossible')
			return
		print('Possible')
		for x in edges:
			print(' '.join(map(str, x)))
solver()()


import math

def primes(a):
	if a < 2:
		return set([])
	initial = [2, 3]
	p = []
	maxp = 0
	for i in initial:
		if i <= a:
			p.append(i)
	for i in range(p[-1] + 1, a + 1):
		isprime = True
		for j in p:
			if j * j > i:
				break
			if i % j == 0:
				isprime = False
				break
		if isprime:
			p.append(i)
	return p

def pfactors(a, ps):
	hasdup = False
	cur = a
	count = 0
	for p in ps:
		if cur == 1:
			break
		if cur % p == 0:
			count += 1
			times = 0
			while cur % p == 0 and cur > 1:
				cur = cur // p
				times += 1
			if times > 1:
				hasdup = True
	return (count, hasdup)

def count(a):
	alls = {}
	ps = primes(a)
	for b in range(2, a // 2 + 1):
		(_, dup) = pfactors(b, ps)
		if dup:
			continue
		alls[b] = a // b
	total = a * (a - 1) // 2
	for (x, y) in alls.items():
		(factors, _) = pfactors(x, ps)
		z = y
		if factors % 2 == 1:
			total -= z * (z - 1) // 2
		else:
			total += z * (z - 1) // 2
	return (total, alls)

def graph(a, b):
	if b < a - 1:
		return 'Impossible'
	if a < 1000:
		(total, alls) = count(a)
		if b > total:
			return 'Impossible'
	num = 0
	edges = []
	for i in range(1, a + 1):
		for j in range(i + 1, a + 1):
			if math.gcd(i, j) == 1:
				edges.append([i, j])
				num += 1
				if num == b:
					break
		if num == b:
			break
	return 'Possible\n' + '\n'.join([' '.join([str(ee) for ee in e]) for e in edges])
(ina, inb) = map(int, input().split(' '))
print(graph(ina, inb))


import sys
from array import array
from math import gcd

def readline():
	return sys.stdin.buffer.readline().decode('utf-8')
(n, m) = map(int, readline().split())
if m < n - 1:
	print('Impossible')
	exit()
ans = []
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if i == 1 or gcd(i, j) == 1:
			ans.append(str(i) + ' ' + str(j))
			m -= 1
			if m == 0:
				sys.stdout.buffer.write(('Possible\n' + '\n'.join(ans)).encode('utf-8'))
				exit()
print('Impossible')


from fractions import gcd
(n, m) = map(int, input().split())
if m < n - 1:
	print('Impossible')
else:
	edges = [(1, i) for i in range(2, n + 1)]
	flag = len(edges) >= m
	for i in range(2, n):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				edges.append((i, j))
				if len(edges) >= m:
					flag = True
					break
		if flag:
			break
	if not flag:
		print('Impossible')
	else:
		print('Possible')
		for (u, v) in edges[:m]:
			print(u, v)


(n, m) = map(int, input().split())

def gcd(p, q):
	if q == 0:
		return p
	else:
		return gcd(q, p % q)
rec = []
num = 0
for i in range(1, n + 1):
	if num == m:
		break
	for j in range(i, n + 1):
		if num == m:
			break
		if j == i:
			continue
		if i == 1:
			rec.append((1, j))
			num += 1
		elif gcd(i, j) == 1:
			rec.append((i, j))
			num += 1
if num < m or n - 1 > m:
	print('Impossible')
else:
	print('Possible')
	for i in range(m):
		print('{} {}'.format(rec[i][0], rec[i][1]))


from math import gcd

def main():
	(n, m) = map(int, input().split())
	if not 1 < n <= m + 1 <= n * (n + 1) // 2:
		(n, m) = (0, 1)
	res = ['Possible']
	for a in range(2, min(n + 1, m + 2)):
		res.append('1 %d' % a)
	m -= min(n - 1, m)
	if m:
		for a in range(n, 2, -1):
			for b in range(a - 1, 1, a % 2 - 2):
				if gcd(a, b) == 1:
					res.append('%d %d' % (b, a))
					m -= 1
					if m <= 0:
						break
			else:
				continue
			break
	print('Impossible' if m else '\n'.join(res))
main()


from fractions import gcd

def main():
	(n, m) = map(int, input().split(' '))
	if m < n - 1 or m > n * (n - 1) // 2:
		print('Impossible')
		return
	ans = []
	for i in range(2, n + 1):
		ans.append([1, i])
	for i in range(2, n):
		if m == len(ans):
			break
		for j in range(i + 1, n + 1):
			if m == len(ans):
				break
			if gcd(i, j) == 1:
				ans.append([i, j])
	if len(ans) < m:
		print('Impossible')
	else:
		print('Possible')
		for (x, y) in ans:
			print(x, y)
main()


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
(n, m) = [int(_) for _ in input().split()]
edges = []
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			edges.append((i, j))
		if len(edges) == m:
			break
	if len(edges) == m:
		break
if len(edges) == m and m >= n - 1:
	print('Possible')
	for edge in edges:
		print('%d %d' % (edge[0], edge[1]))
else:
	print('Impossible')


from math import gcd
from itertools import islice

def get_all(n):
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				yield (i, j)

def solve(n, m):
	x = list(islice(get_all(n), m))
	if len(x) == m >= n - 1:
		return x
res = solve(*map(int, input().split()))
if res is not None:
	print('Possible')
	for e in res:
		print(*e)
else:
	print('Impossible')


(n, m) = input().split(' ')
(n, m) = (int(n), int(m))
from math import gcd
tot = 0
a = 1
b = 2
A = []
while tot < m:
	if gcd(a, b) == 1:
		A.append((a, b))
		tot += 1
	b += 1
	if b > n:
		a += 1
		b = a + 1
	if a >= n:
		break
if tot == m and m >= n - 1 and (n != 1):
	print('Possible')
	for i in range(tot):
		print(A[i][0], end=' ')
		print(A[i][1])
else:
	print('Impossible')


from fractions import *
(n, m) = map(int, input().split())
(a, c) = ('Possible', 0)
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			c += 1
			a += '\n%d %d' % (i, j)
			if c == m:
				break
	if c == m:
		break
print(a if c == m and m > n - 2 else 'Impossible')


from itertools import repeat
from math import gcd

def p(n, m):
	if m < n - 1:
		return 'Impossible'
	ans = list(zip(repeat(1), range(2, n + 1)))
	for i in range(2, n + 1):
		for j in range(i + 1, n + 1):
			if gcd(i, j) == 1:
				ans.append([i, j])
			if len(ans) >= m:
				break
		if len(ans) >= m:
			break
	if len(ans) < m:
		return 'Impossible'
	return '\n'.join(['Possible', *(' '.join((str(x) for x in pair)) for pair in ans[:m])])
print(p(*map(int, input().split())))


from array import array
from sys import stdin
import bisect
from bisect import *
import itertools
from itertools import *

def scan_gen():
	for line in stdin:
		yield from iter(line.split())
scan = scan_gen()

def nint():
	return int(next(scan))

def nintk(k):
	return tuple((nint() for _ in range(k)))

def nfloat():
	return float(next(scan))

def intar_init(size):
	return array('i', [0]) * size

def intar(size=None):
	if size == None:
		size = nint()
	arr = intar_init(size)
	for x in range(size):
		arr[x] = nint()
	return arr

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def solve():
	(n, m) = nintk(2)
	if m < n - 1:
		print('Impossible')
		return
	res = []
	for x in range(2, n + 1):
		res += [(1, x)]
		m -= 1
	for (x, y) in product(range(2, n + 1), range(2, n + 1)):
		if x < y and gcd(x, y) == 1:
			if m == 0:
				break
			res += [(x, y)]
			m -= 1
			if m == 0:
				break
	if m != 0:
		print('Impossible')
	else:
		print('Possible')
		for p in res:
			print(*p)
solve()


import collections

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
(n, m) = tuple(map(int, input().split()))
if m < n - 1:
	print('Impossible')
	exit()
edges = 0
flag = False
graph = collections.defaultdict(list)
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if gcd(i, j) == 1:
			graph[i].append(j)
			edges += 1
			if edges == m:
				flag = True
				break
	if flag:
		break
if edges == m:
	print('Possible')
	for i in graph:
		for j in graph[i]:
			print(str(i) + ' ' + str(j))
else:
	print('Impossible')


(n, m) = map(int, input().split())
import math
if m < n - 1 or m > (n - 1) * n // 2:
	print('Impossible')
	exit()
ans = [[1, i] for i in range(2, n + 1)]
m -= n - 1
i = 0
b = 2
k = b + 1
while i < m and b < n:
	if math.gcd(b, k) == 1:
		i += 1
		ans.append([b, k])
	k += 1
	if k == n + 1:
		b += 1
		k = b + 1
if i == m:
	print('Possible')
	for i in ans:
		print(*i)
else:
	print('Impossible')