Codeforces 1009D：Relatively Prime Graph

#include<cstdio>
using namespace std;

#define min(a,b) a<b?a:b
const int maxn=610;

int prime[maxn];
int phi[maxn];
int tot;
int n,m;

void Euler(){
  
  int node=min(n,600);
  for(int i=2;i<=node;i++){
    
    if(!phi[i]){
      
      prime[tot++]=i;
      phi[i]=i-1;
    }
    for(int j=0;j<tot&&i*prime[j]<=node;j++){
      
      if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
      else{
        
        phi[i*prime[j]]=phi[i]*prime[j];
        break;
      }
    }
  }
}

inline int gcd(int a,int b){
  
  return b==0?a:gcd(b,a%b);
}

int main(){
  
  scanf("%d%d",&n,&m);
  Euler();
  int i;
  int num=0;
  for(i=2;i<=n;i++){
    
    num+=phi[i];
    if(num>=m) break;
  }
  if(m<n-1 || i>n) printf("Impossible\n");
  else{
    
    printf("Possible\n");
    for(int i=1;i<n;i++) printf("%d %d\n",i,i+1);
    m-=(n-1);
    int node=min(600,n);
    for(int i=1;i<=node&&m;i++){
      
      for(int j=i+1;j<=node&&m;j++){
        
        if(gcd(i,j)==1&&i+1!=j) printf("%d %d\n",i,j),m--;
      }
    }
  }
}