Codeforces 1009D：Relatively Prime Graph

点虽然最多会有100000个点，但是边最多也只有100000条，所以我用欧拉函数的前缀和求得，最多不超过600个点，就可以有超过100000条边的情况，这样从边突破，时间复杂度就满足了。
我们可以利用欧拉函数，得到n个点，最多可能有多少条边，即 区间 [2,n] 的phi[i]的和（phi[]为欧拉函数数组）
所以当 m小于 n-1（即n个点都连接不了） 或者 大于最多条边，就不可能存在m条边的情况
并且首先要保证有n个点，即先连接相邻的点 即（i,i+1) (1<=i<=n-1) ，再连接其他边即可

#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--;}}}
}