模拟赛 T3，赛时觉得题目太长、没暴力分，一字没写。赛后仔细看题 10min 不到就切了qwq。

题意：初始给定 $N$ 个点，要支持 $Q$ 次查询或修改。

• 修改：给定点 $A,B$，如果它们连通，则将连接它们的所有最短路的所有边权赋为 $1$。如果不连通，用一条 $0$ 边连接它们。
• 查询：给定点 $A,B$，如果它们连通，求用它们进行修改操作会改变多少条边。如果不连通，输出 $-1$。

首先有个简单的发现：因为修改不会产生环，所以这个图一定是个森林，最短路也就只有一条。

不妨离线，把最后的森林建好，然后用一个超级根连接每棵树的根，这样就变成了树上问题。

判断是否连通可以用并查集来做，然后就变成了一个树上链修改，链查询，直接树剖。

:::success[AC 代码]{open}

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
using ll= long long;
const int N=100005,Q=300005;
int val[N<<2],tag[N<<2]; // 线段树，初始全 1，区间赋 0，区间求和。
void pushup(int u) {
	val[u]=val[u<<1]+val[u<<1|1];
}
void app(int u) {
	val[u]=0,tag[u]=1;
}
void pushdown(int u) {
	if(tag[u]) {
		app(u<<1);
		app(u<<1|1);
		tag[u]=0;
	}
}
void build(int u,int l,int r) {
	if(l==r) return val[u]=1,void();
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void upd(int u,int l,int r,int s,int t) {
	if(s<=l&&r<=t) return app(u),void();
	pushdown(u);
	if(s<=mid) upd(u<<1,l,mid,s,t);
	if(t>mid) upd(u<<1|1,mid+1,r,s,t);
	pushup(u);
}
int query(int u,int l,int r,int s,int t) {
	if(s<=l&&r<=t) return val[u];
	pushdown(u);
	if(t<=mid) return query(u<<1,l,mid,s,t);
	if(s>mid) return query(u<<1|1,mid+1,r,s,t);
	return query(u<<1,l,mid,s,t)+query(u<<1|1,mid+1,r,s,t);
}
int n,q,t[Q],a[Q],b[Q];
int dfn[N],siz[N],fa[N],son[N],top[N],dep[N];
vector<int> g[N];
void adde(int u,int v) { // 建树
	g[u].push_back(v);
	g[v].push_back(u);
}
void init(int u,int p) {
	fa[u]=p,siz[u]=1,dep[u]=dep[p]+1;
	for(int& v: g[u]) if(v!=p) {
		init(v,u);
		if(siz[v]>siz[son[u]]) son[u]=v;
		siz[u]+=siz[v];
	}
}
int ttot;
void dfs1(int u,int to) {
	dfn[u]=++ttot,top[u]=to;
	if(!son[u]) return;
	dfs1(son[u],to);
	for(int& v: g[u])
		if(!dfn[v])
			dfs1(v,v);
}
int bfa[N]; // 并查集
void binit() {
	for(int i=1;i<=n;i++)
		bfa[i]=i;
}
int find(int u) {
	return bfa[u]==u?u:(bfa[u]=find(bfa[u]));
}
void merg(int u,int v) {
	bfa[find(u)]=find(v);
}
void upd(int u,int v) { // 树剖
	while(top[u]!=top[v]) {
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		upd(1,1,n,dfn[top[u]],dfn[u]);
		u=fa[top[u]];
	}
	if(u==v) return;
	if(dep[u]>dep[v]) swap(u,v);
	upd(1,1,n,dfn[u]+1,dfn[v]);
}
int query(int u,int v) {
	int ret=0;
	while(top[u]!=top[v]) {
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ret+=query(1,1,n,dfn[top[u]],dfn[u]);
		u=fa[top[u]];
	}
	if(u==v) return ret;
	if(dep[u]>dep[v]) swap(u,v);
	return ret+query(1,1,n,dfn[u]+1,dfn[v]);
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>q; n++;
	binit();
	for(int i=1;i<=q;i++) {
		cin>>t[i]>>a[i]>>b[i];
		if(t[i]==1&&find(a[i])!=find(b[i]))
			merg(a[i],b[i]),adde(a[i],b[i]);
		if(q==1) cerr<<i<<'\n';
	}
	for(int i=1;i<n;i++)
		if(find(i)==i)
			adde(i,n);
	binit();
	build(1,1,n);
	init(n,0);
	dfs1(n,n);
	for(int i=1;i<=q;i++) {
		if(t[i]==1) {
			if(find(a[i])!=find(b[i])) merg(a[i],b[i]);
			else upd(a[i],b[i]);
		} else {
			if(find(a[i])!=find(b[i])) cout<<"-1\n";
			else cout<<query(a[i],b[i])<<'\n';
		}
	}
	return 0;
}

:::