#include<bits/stdc++.h>
using namespace std;
mt19937_64 mrd(time(0));
const int N=1e9+7,inf=1e9,M=6e7;
int pri[M],tot,fa[200010];
bool vis[N];
void init(){for(int i=2;i<=1e9;i++){if(!vis[i]) pri[++tot]=i;for(int j=1;j<=tot&&i*pri[j]<=1e9;j++){vis[i*pri[j]]=1;if(i%pri[j]==0) break;}}
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
signed main(){freopen("1.in","w",stdout);int n=200000,m=200000;init();printf("%d %d\n",n,m);for(int i=1;i<=n;i++){int x=mrd()%tot+1;int y=pri[x];if(y<=1e4) {if(mrd()&1)y=y*(mrd()%10000+1);elsey=y*y; }else{int bei=inf/y;if(mrd()&1)y=y*(mrd()%bei+1); }printf("%d ",y);}puts("");//可替换部分for(int i=1;i<=n;i++)fa[i]=i;int tot=0;while(tot<n-1){int u=mrd()%n+1,v=mrd()%n+1;if(find(u)==find(v)) continue;tot++;fa[find(u)]=find(v);printf("%d %d\n",u,v);}//for(int i=1;i<=m;i++){int x=mrd()%n+1,y=mrd()%n+1;printf("%d %d\n",x,y);}return 0;
}
/*
tree1:深度可调
for(int i=2;i<=n;i++)
{int y=i-100+mrd()%100;printf("%d %d\n",i,max(1,y));
}
tree2:log深度
for(int i=1;i<=n;i++)
fa[i]=i;
int tot=0;
while(tot<n-1)
{int u=mrd()%n+1,v=mrd()%n+1;if(find(u)==find(v)) continue;tot++;fa[find(u)]=find(v);printf("%d %d\n",u,v);
}
tree3:链
for(int i=1;i<n;i++)
printf("%d %d\n",i,i+1);
tree4:菊花图
*/
