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.

5 6

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

6 12

Impossible

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