#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
struct query{
int t,l,r;
};
query q[1000005];
vector <int> z[1000005];
struct dsu{
int par[1000005];
int sz[1000005];
void init(){
for (int i=1;i<=a;i++){
par[i]=i;
sz[i]=1;
}
}
int find(int u){
if (par[u]==u){
return u;
}
return par[u]=find(par[u]);
}
bool join(int x,int y){
x=find(x);
y=find(y);
if (x==y){
return false;
}
if (sz[x]<sz[y]){
swap(x,y);
}
sz[x]+=sz[y];
par[y]=x;
return true;
}
};
dsu d;
int lead[1000005];
int high[1000005];
int big[1000005];
int head[1000005];
int par[1000005];
int rev[1000005];
int pos[1000005];
int curpos;
bool vis[1000005];
int child[1000005];
void dfs(int i,int parent){
child[i]=1;
big[i]=-1;
for (auto p:z[i]){
if (p==parent){
continue;
}
high[p]=high[i]+1;
dfs(p,i);
child[i]+=child[p];
if (big[i]==-1 && child[big[i]]<child[p]){
big[i]=p;
}
}
}
void decompose(int i,int parent,int h){
vis[i]=true;
curpos++;
pos[i]=curpos;
rev[curpos]=i;
head[i]=h;
par[i]=parent;
if (big[i]!=-1){
decompose(big[i],i,h);
}
for (auto p:z[i]){
if (p==parent || p==big[i]){
continue;
}
decompose(p,i,p);
}
}
int f[4000005];
int lazy[4000005];
void push(int id,int l,int r){
if (lazy[id]!=0){
lazy[id*2]=lazy[id];
lazy[id*2+1]=lazy[id];
int mid=(l+r)/2;
f[id*2]=(mid-l+1);
f[id*2+1]=(r-mid);
lazy[id]=0;
}
}
void update(int id,int l,int r,int x,int y){
if (x>r || y<l){
return;
}
if (l>=x && y>=r){
f[id]=(r-l+1);
lazy[id]=1;
return;
}
int mid=(l+r)/2;
push(id,l,r);
update(id*2,l,mid,x,y);
update(id*2+1,mid+1,r,x,y);
f[id]=f[id*2]+f[id*2+1];
}
int get(int id,int l,int r,int x,int y){
if (x>r || y<l){
return 0;
}
if (l>=x && y>=r){
return f[id];
}
int mid=(l+r)/2;
push(id,l,r);
return get(id*2,l,mid,x,y)+get(id*2+1,mid+1,r,x,y);
}
void query1(int x,int y){
int l=x,r=y;
int cnt=0;
while (head[x]!=head[y]){
if (high[head[x]]<high[head[y]]){
swap(x,y);
}
cnt+=get(1,1,curpos,pos[head[x]],pos[x]);
x=par[head[x]];
}
if (high[x]>high[y]){
swap(x,y);
}
cnt+=get(1,1,curpos,pos[x]+1,pos[y]);
cout << high[l]+high[r]-2*high[x] - cnt << "\n";
}
void query2(int x,int y){
while (head[x]!=head[y]){
if (high[head[x]]<high[head[y]]){
swap(x,y);
}
update(1,1,curpos,pos[head[x]],pos[x]);
x=par[head[x]];
}
if (high[x]>high[y]){
swap(x,y);
}
update(1,1,curpos,pos[x]+1,pos[y]);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
d.init();
for (int i=1;i<=b;i++){
int c,x,y;
cin >> c >> x >> y;
if (c==1){
if (d.join(x,y)){
z[x].push_back(y);
z[y].push_back(x);
}
}
q[i]={c,x,y};
}
for (int i=1;i<=a;i++){
if (!vis[i]){
lead[i]=1;
dfs(i,0);
}
}
for (int i=1;i<=a;i++){
if (lead[i]){
decompose(i,0,i);
}
}
d.init();
for (int i=1;i<=b;i++){
auto [c,x,y]=q[i];
if (c==1){
if (!d.join(x,y)){
query2(x,y);
}
}else{
int l=d.find(x),r=d.find(y);
if (l!=r){
cout << -1 << "\n";
continue;
}
query1(x,y);
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |