CF1009D.Relatively Prime Graph

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.

我们称一个无向图 $G = (V, E)$ 是互质图，当且仅当对每条边 $(v, u) \in E$，都有 $\mathrm{GCD}(v, u) = 1$（即 $v$ 与 $u$ 的最大公约数为 $1$）。若某对顶点 $v$ 和 $u$ 之间没有边，则 $\mathrm{GCD}(v, u)$ 的值无关紧要。顶点编号为 $1$ 到 $|V|$。

请构造一个包含 $n$ 个顶点和 $m$ 条边的互质图，要求该图是连通的，且不包含自环或重边。

如果不存在满足给定顶点数和边数的有效图，则输出 "Impossible"。

若存在多个合法答案，输出任意一个即可。

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.

唯一的一行包含两个整数 $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:

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.

如果不存在满足给定顶点数和边数的有效图，则输出 "Impossible"。

否则，按以下格式输出答案：

第一行应包含单词 "Possible"。

接下来的 $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$。

若存在多个可行解，则输出任意一个即可。

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

以下是第一个示例中图的表示：