← 返回题目列表

Codeforces · 1009/D

D. 相对素图

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

我们称无向图 $$$G = (V, E)$$$ 相对素当且仅当对于每条边 $$$(v, u) \in E$$$  $$$GCD(v, u) = 1$$$ ($$$v$$$ 和 $$$u$$$ 的最大公约数是 $$$1$$$)。 If there is no edge between some pair of vertices $$$v$$$ and $$$u$$$ then the value of $$$GCD(v, u)$$$ doesn't matter.顶点编号从 $$$1$$$ 到 $$$|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".

如果有多个答案,则打印其中任何一个。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — 顶点数和边数。

输出

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:

第一行应包含“可能”一词。

接下来的 $$$m$$$ 行中的第 $$$i$$$ 行应包含结果图的第 $$$i$$$ 边 $$$(v_i, u_i)$$$ ($$$1 \le v_i, u_i \le n, v_i \neq u_i$$$)。对于每对 $$$(v, u)$$$,不能有更多对 $$$(v, u)$$$ 或 $$$(u, v)$$$。顶点编号从 $$$1$$$ 到 $$$n$$$。

如果有多个答案,则打印其中任何一个。

示例

输入 #1

5 6

输出 #1

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

输入 #2

6 12

输出 #2

Impossible

注意

Here is the representation of the graph from the first example: