提供一个代码短小、便于实现的做法。

看到数据范围点数的限制不难推出点数是 $O(\sqrt{k})$ 量级的，因为一个大小为 $n$ 的环上完美点对数为 $\dfrac{n(n-1)}{2}$，于是考虑构造环。

具体地，不断构造当前可构造的最大的环，不妨设环大小为 $x$，去除已经构造的环的贡献的 $k$ 为 $k'$，有 $\dfrac{x(x-1)}{2}\le k$，解得 $x\le\dfrac{1+\sqrt{8k+1}}{2}$，即 $x_{\max}=\left\lfloor\dfrac{1+\sqrt{8k+1}}{2}\right\rfloor$。

但是有个注意点：题目要求构造出的图必须连通，于是在相邻两个环之间连边即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int k,c=0; cin>>k;
  if(k){
    vector<pair<int,int> > e; // 存边
    while(k){
      int x=(sqrt(k<<3|1)+1)/2;
      for(int i=0;i<x;i++)
        e.emplace_back(c+i,c+(i+1)%x);
      if(c)e.emplace_back(c-1,c);
      c+=x,k-=x*(x-1)>>1; // 更新点数和 k
    } // 不断构造
    cout<<c<<' '<<e.size()<<endl;
    for(auto [u,v]:e)cout<<u+1<<' '<<v+1<<'\n';
  }
  else cout<<"2 1\n1 2\n";
  return 0;
}