CF1009D 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$）。

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