我的思路：

对于每一只奶龙都以其为起点构建一条长度为 $k+1$ 的链，链的后面是没有奶龙的结点。根据有解判定可知 $m(k+1) \ge n$，所以这些链一定能在 $k$ 步时覆盖所有没有奶龙的点。现在我们得到 $m$ 条散链，为了凑够边数，考虑把每条链都连回 $a_1$。

经过评测尝试， 为什么一定要连回 $a_1$，其他的都不行？求教

部分ac code：

vector<int> to(n + 1, 0); // 存储每个点的指向
// 标记是否与奶龙连边
vector<bool> vis(n + 1, 0); 
for(int i = 1; i <= m; i ++){
  vis[a[i]] = true;
}
// 给每只奶龙都连一个普通点
int now = 1; // 普通点计数器
for(int i = 1; i <= m; i ++){ 
  int s = a[i]; // 下一次连边的起点
  for(int j = 1; j <= k && now <= n; ){
    if(!vis[now]){
      to[s] = now; // 继续向普通点连边
      s = now; // 下一次连边的起点为now
      j ++;
    }
    now ++;
  }
  to[s] = a[1]; // 把每条链的结尾连向a[1]？？？
}
for(int i = 1; i <= n; i ++){
  cout << i << ' ' << to[i] << '\n';
}