某些题解在合并时没有新建节点更新 dep，复杂度是错的，见 这篇讨论。

第一篇题解 第二篇题解 正确记录。

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

//#define fo(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout); 
#define fo(x) freopen(#x".in", "w", stdout); // freopen(#x".in", "r", stdin);

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;

int n = 5e4, m = 2e5, k = 400;
int C;

vector<tuple<int, int, int>> A;

void push(int a, int b, int c = 0) {
	A.emplace_back(a, b, c);
}

int main()
{
	fo(DSU)
	for (int i = 1; i < k; ++i) {
		for (int j = 0; j < k - i; ++j) {
			push(1, n - j - 1, n - j), push(2, 0);
		}
	}
	push(1, n - k - 1, n - k);
	for (int i = k; i >= 0; --i) push(1, n - i - 1, n - i);
	while (A.size() < m) {
		int u = n - rnd() % (k + 1), v = n - rnd() % (k + 1);
		push(3, u, v);
	}
    printf("%d %d", n, (int)A.size());
	for (auto p : A) {
		if (get<0>(p) == 2) printf("\n%d %d", get<0>(p), get<1>(p));
		else printf("\n%d %d %d", get<0>(p), get<1>(p), get<2>(p));
	}
    return 0;
}

假设我们要构造出一条长度为 $k+1$ 的链：

取 $k$ 个节点，进行 $k-1$ 次连边之后再撤销的操作，这样有 $k-1$ 个节点的 dep 会变成 $2$，再进行 $k-2$ 次这样的操作，会有 $k-2$ 个节点的 dep 会变成 $3$。

以此类推，最后可以得到 $k$ 个 dep 分别为 $1 \dots k$ 的节点。

最后再加入一个新节点，依次与 dep 为 $1 \dots k$ 的节点连边，就可以得到一条长度为 $k+1$ 的链。