https://www.luogu.com.cn/blog/128606/solution-p3346

这篇题解实际的时间复杂度应为 $O(k^2n)$，在两端挂各 $\frac{k}{2}$ 个叶子节点，中间连长为 $O(n)$ 的链就能卡掉

以下为 generator

#include<bits/stdc++.h>

#define ll long long

using namespace std;

mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}

vector<pair<int,int> >E;
#define fi first
#define se second
#define mk make_pair
void adde(int x,int y){E.emplace_back(mk(x,y));}
signed main(void){
	
	freopen("hack.in","w",stdout);
	int n=100000;int c=10;
	cout<<n<<" "<<c<<endl;
	for(int i=1;i<n;i++)cout<<randint(0,c-1)<<" ";cout<<randint(0,c-1)<<endl;
	for(int i=1;i<=10;i++)adde(i,11);
	for(int i=13;i<=22;i++)adde(i,12);
	adde(11,23),adde(12,n);
	for(int i=23;i<n;i++)adde(i,i+1);
	assert(E.size()==n-1);
	for(auto t:E)cout<<t.fi<<" "<<t.se<<endl;

	return 0;
}