Generator：

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N = 1e5 , K = 2 , T = 0; cout << N << ' ' << K << ' ' << T << endl; int cnt = 1;
	for(int i = 1 ; i <= 2e4 ; ++i){int pre = 1; for(int j = 0 ; j < 3 ; ++j){int p = ++cnt; cout << pre << ' ' << p << endl; pre = p;}}
	while(cnt < N){++cnt; cout << 1 << ' ' << cnt << endl;}
	return 0;
}

叉掉了亿些贪心 bfs 不去重的

原理：在 1 上造一个菊花加上若干条长度为 3 的链，这样每次贪心都会选长度为 3 的链的根的邻居，此时如果 bfs 不去重就会每次都 bfs 到 1 上的菊花，就可以卡到 $O(n^2)$ 了。

建议加入数据并撤下以下题解：

https://www.luogu.com.cn/blog/TheShadow/p3942-jiang-jun-ling-ti-xie
https://garody.blog.luogu.org/solution-p3942
https://nanfengzjy.blog.luogu.org/solution-p3942
https://www.luogu.com.cn/blog/user18441/solution-p3942
https://www.luogu.com.cn/blog/user47378/solution-p3942
https://www.luogu.com.cn/blog/user3846/solution-p3942
https://www.luogu.com.cn/blog/poorpool/solution-p3942
https://www.luogu.com.cn/blog/Thinking/solution-p3942
https://www.luogu.com.cn/blog/174469/solution-p3942
https://www.luogu.com.cn/blog/new2zy/solution-p3942

顺便，只要动态更新一下每个点到当前选中的所有点的距离最小值加个剪枝就可以做到 $O(nk)$，在 $k$ 任意的情况下这玩意的复杂度是 $O(n\sqrt {n})$ 的，大家可以自己算算。