#include #include #include #include #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() using namespace std; using namespace atcoder; using ll=long long; using ld=long double; using vll=vector; using vvll=vector; using vi=vector; using vvi=vector; using pll=pair; // using mint=modint; // using BoostPoint=boost::polygon::point_data; // using Voronoi=boost::polygon::voronoi_diagram; #line 2 "data-structure/union-find-with-potential.hpp" template struct UnionFindWithPotential { vector dat; vector pot; UnionFindWithPotential(int N) : dat(N, -1), pot(N, T()) {} int root(int x) { if (dat[x] < 0) return x; int r = root(dat[x]); pot[x] += pot[dat[x]]; return dat[x] = r; } // return P(x) - P(root(x)) T potential(int x) { root(x); return pot[x]; } bool same(int x, int y) { return root(x) == root(y); } // return P(x) - P(y) T diff(int x, int y) { return potential(x) - potential(y); } // s.t. P(x) = P(y) + p // return Satisfiablility bool merge(int x, int y, T p) { p += potential(y) - potential(x); x = root(x), y = root(y); if (x == y) return p == T(); if (dat[x] < dat[y]) swap(x, y), p = -p; dat[y] += dat[x]; dat[x] = y; pot[x] = p; return true; } // return size of CC including x int size(int x) { return -dat[root(x)]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N,Q; cin>>N>>Q; vll add(N,0); UnionFindWithPotentialuf(N); while(Q--){ ll t,a,b; cin>>t>>a>>b; --a; if(t==1){ --b; ll x=uf.root(a),y=uf.root(b); if(x==y)continue; uf.merge(x,y,add[x]-add[y]); }else if(t==2){ add[uf.root(a)]+=b; }else{ cout<