Description：

一张连通图， $q$ 次询问从两个点 $x$ 和 $y$ 出发，希望经过的点(不重复)数量等于 $z$ ，经过的边最大编号最小是多少。

$1\leqslant n\leqslant 10^5$

Solution：

最大值最小显然二分，那么问题就变成了判断只经过编号 $\leqslant k$ 的边 $x$ 和 $y$ 是否连通以及他们所在的联通块是否有 $\geqslant z$ 个点。这个显然是可以并查集做的，但是每次暴力重构并查集复杂度显然是不靠谱的，一种方法是把并查集可持久化，每次在对应的并查集上查一下就行了，但是要写主席树，另一种方法是整体二分，也就是说维护一个支持撤销的并查集，然后每次递归到二分形成的二叉树的叶子的时候就把他们两个连起来，这样每次只操作这个区间内的边就能得到所有编号 $\leqslant k$ 的边的联通情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,p;

#define MAXN 100010

struct edges

{

	int u,v,id;

}e[MAXN];

namespace UFS

{

	int f[MAXN],siz[MAXN],rnk[MAXN];

	int find(int x){return (x == f[x] ? x : find(f[x]));}

	int stack[MAXN * 2],top = 0;

	void init()

	{

		for(int i = 1;i <= n;++i)

		{

			f[i] = i;

			siz[i] = 1;

		}

		return;

	}

	void merge(int a,int b)

	{

		int p = find(a),q = find(b);

		if(p == q)return;

		if(rnk[p] > rnk[q])swap(p,q);

		f[p] = q;siz[q] += siz[p];

		stack[++top] = p;

		if(rnk[p] == rnk[q])

		{

			++rnk[q];

			stack[++top] = -q;

		}

		return;

	}

	void reset(int pos)

	{

		while(top > pos)

		{

			int k = stack[top];--top;

			if(k > 0)

			{

				siz[f[k]] -= siz[k];

				f[k] = k;

			}

			else --rnk[-k];

		}

	}

}

struct query

{

	int x,y,z,id;

}q[MAXN],q1[MAXN],q2[MAXN];

int ans[MAXN];

void solve(int ql,int qr,int L,int R)

{

	if(L == R)

	{

		UFS::merge(e[L].u,e[L].v);

		for(int i = ql;i <= qr;++i)ans[q[i].id] = L;

		return;

	}

	using namespace UFS;

	int mid = ((L + R) >> 1);

	int pos = top;

	for(int i = L;i <= mid;++i)merge(e[i].u,e[i].v);

	int qcnt1 = 0,qcnt2 = 0;

	for(int i = ql;i <= qr;++i)

	{

		if(find(q[i].x) == find(q[i].y))

		{

			if(siz[find(q[i].x)] < q[i].z)q2[++qcnt2] = q[i];

			else q1[++qcnt1] = q[i];

		}

		else

		{

			if(siz[find(q[i].x)] + siz[find(q[i].y)] < q[i].z)q2[++qcnt2] = q[i];

			else q1[++qcnt1] = q[i];

		}

	}

	reset(pos);

	int cur = ql;

	for(int i = 1;i <= qcnt1;++i)q[cur++] = q1[i];

	for(int i = 1;i <= qcnt2;++i)q[cur++] = q2[i];

	solve(ql,ql + qcnt1 - 1,L,mid);

	solve(ql + qcnt1,qr,mid + 1,R);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	UFS::init();

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&e[i].u,&e[i].v);

		e[i].id = i;

	}

	scanf("%d",&p);

	for(int i = 1;i <= p;++i)

	{

		scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);

		q[i].id = i;

	}

	solve(1,p,1,m);

	for(int i = 1;i <= p;++i)printf("%d\n",ans[i]);

	return 0;

}