#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back const int N=3e5+50; vector<int>E[N]; int n,q; array<int,3>Qs[N]; struct DSU{ int par[N]; void Init(){for(int i=0;i<N;i++)par[i]=i;} DSU(){Init();} int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);} void US(int u,int v){par[FS(u)]=v;} }dsu; struct SegTree{ int root,nc,lc[2*N],rc[2*N],sum[2*N],lazy[2*N]; void update(int &c,int ss,int se,int x){ if(!c)c=++nc,lazy[c]=-1; if(x!=-1){ sum[c]=(se-ss+1)*x; lazy[c]=x; } } void push(int &c,int ss,int se){ if(!c)c=++nc,lazy[c]=-1; int mid=ss+se>>1; update(lc[c],ss,mid,lazy[c]); update(rc[c],mid+1,se,lazy[c]); lazy[c]=-1; } void Update(int &c,int ss,int se,int qs,int qe,int x){ if(!c)c=++nc,lazy[c]=-1; if(qs>qe||qe<ss||se<qs)return; if(qs<=ss&&se<=qe){update(c,ss,se,x);return;} int mid=ss+se>>1;push(c,ss,se); Update(lc[c],ss,mid,qs,qe,x); Update(rc[c],mid+1,se,qs,qe,x); sum[c]=sum[lc[c]]+sum[rc[c]]; } int Get(int &c,int ss,int se,int qs,int qe){ if(!c)c=++nc,lazy[c]=-1; if(qs>qe||qe<ss||se<qs)return 0; if(qs<=ss&&se<=qe)return sum[c]; int mid=ss+se>>1;push(c,ss,se); return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe); } }ST; int head[N],depth[N],sajz[N],par[N]; void DFS(int u,int p=0){ depth[u]=depth[p]+1; par[u]=p; for(auto &i:E[u])if(i==p){swap(i,E[u].back());break;} if(p!=0)E[u].pop_back(); sajz[u]=1; for(auto i:E[u])DFS(i,u),sajz[u]+=sajz[i]; } int in[N],out[N],tajm; void HLD(int u){ in[u]=++tajm; int mx=0,v=0; for(auto i:E[u])if(sajz[i]>mx)mx=sajz[i],v=i; for(auto &i:E[u])if(i==v){swap(i,E[u][0]);break;} if(head[u]==0)head[u]=u; if(v>0)head[v]=head[u]; for(auto i:E[u])HLD(i); out[u]=tajm; } int LCA(int u,int v){ while(head[u]!=head[v]){ //printf("- %i %i\n",u,v); if(depth[head[u]]<depth[head[v]])swap(u,v); u=par[head[u]]; } return depth[u]<depth[v]?u:v; } int Calc(int u,int c){ int res=0; while(head[u]!=head[c]){ res+=ST.Get(ST.root,1,tajm,in[head[u]],in[u]); u=par[head[u]]; } res+=ST.Get(ST.root,1,tajm,in[c]+1,in[u]); return res; } void Upd(int u,int c,int x){ while(head[u]!=head[c]){ ST.Update(ST.root,1,tajm,in[head[u]],in[u],0); u=par[head[u]]; } ST.Update(ST.root,1,tajm,in[c]+1,in[u],0); } int main(){ scanf("%i%i",&n,&q); for(int i=1;i<=q;i++)scanf("%i%i%i",&Qs[i][0],&Qs[i][1],&Qs[i][2]); for(int i=1;i<=q;i++){ auto [t,u,v]=Qs[i]; if(t==1&&dsu.FS(u)!=dsu.FS(v)){ dsu.US(u,v); E[u].pb(v); E[v].pb(u); } } int root=n+1; for(int i=1;i<=n;i++)if(dsu.FS(i)!=dsu.FS(root)){ dsu.US(i,root); E[i].pb(root); E[root].pb(i); } DFS(root); HLD(root); //for(int i=1;i<=n;i++)printf("%i->%i\n",i,par[i]); //for(int i=1;i<=n;i++)printf("head[%i]=%i\n",i,head[i]); dsu.Init(); ST.Update(ST.root,1,tajm,1,tajm,1); for(int i=1;i<=q;i++){ auto [t,u,v]=Qs[i]; if(t==1){ if(dsu.FS(u)!=dsu.FS(v))dsu.US(u,v); else{ int c=LCA(u,v); Upd(u,c,0); Upd(v,c,0); } } else{ if(dsu.FS(u)==dsu.FS(v)){ int c=LCA(u,v); //printf("%i: %i %i\n",c,Calc(u,c),Calc(v,c)); int res=Calc(u,c)+Calc(v,c); printf("%i\n",res); } else printf("-1\n"); } } return 0; }

road_development.cpp: In function 'int main()':
road_development.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%i%i",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
road_development.cpp:97:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     for(int i=1;i<=q;i++)scanf("%i%i%i",&Qs[i][0],&Qs[i][1],&Qs[i][2]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~