Relatively Prime Graph

题意翻译

## 题目描述 我们将一个无向图称作互质图，当且仅当对于其中每一条边$(v, u)$有$v$和$u$互质（也即$GCD(v,u)=1$）。当两个顶点之间没有边时不需要考虑。顶点从1开始标号。 现在给你$n$个顶点和$m$条边，要求你建立一个无重边和自环并且连通的互质图，如果无法构造输出"Impossible"，对于多种可能的答案输出任意一种即可。 ### 输入格式： 顶点数$n$，边数$m$。($1≤n,m≤10^5$) ### 输出格式： 如果不存在答案输出"Impossible"。否则第一行输出"Possible"，接下来m行每行输出$v_i, u_i$（$1≤v_i,u_i≤n,v_i≠u_i$）。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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: