因为我的写法比较 sb，每次合并需要更新 x 和 y 两个点的 fa 和 siz，这样最多需要 $2m\log n\approx8\times10^6$ 个节点，但是我忘了前面的那个 $2$，只开了 $4\times10^6$ 个点就过掉了（讲个笑话：我一开始是从可持久化数组 copy 板子来的，一开始只开了 $n\log n\approx2\times10^6$ 个点）。

附上 hack 生成器：

#include<bits/stdc++.h>
void writeln(int arg) {printf("%d\n", arg);}
template<typename ...Typ2> void writeln(int arg, Typ2 ...args) {
	printf("%d ", arg), writeln(args...);
}
int main() {
	int n = 1e5, q = 2e5; writeln(n, q);
	for(int i = 1; i < 1e5; i++) writeln(1, i, i + 1);
	writeln(2, 0);
	for(int i = 1; i < 5e4; i++) writeln(1, i, i + 1);
	writeln(2, 149999);//place_holder
	for(int i = 5e4 + 1; i < 1e5; i++) writeln(1, i, i + 1);
	writeln(3, 1, 1e5);
}

参考了 #13 把我 $2\times10^6$ 个点的代码（没开 O2）卡 wa 的连边方式，再次表示感谢。

错误输出：（没开 O2）

1

正确输出：

0