// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind_with_potential
#include "DataStructure/weighted_union_find.hpp"
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
int main()
{
int N, Q;
cin >> N >> Q;
WeightedUnionFind<atcoder::modint998244353> wuf(N);
for (int i = 0; i < Q; i++)
{
int t;
cin >> t;
if (t == 0)
{
int u, v, x;
cin >> u >> v >> x;
if (wuf.valid(u, v, x))
{
wuf.merge(u, v, x);
}
cout << wuf.valid(u, v, x) << endl;
}
if (t == 1)
{
int x, y;
cin >> x >> y;
if (!wuf.same(x, y))
{
cout << "-1" << endl;
}
else
{
cout << wuf.diff(x, y).val() << endl;
}
}
}
return 0;
}
#line 1 "test/DataStructure/weighted_union_find/yosupo-unionfind_with_potential.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind_with_potential
#line 1 "DataStructure/weighted_union_find.hpp"
#include <bits/stdc++.h>
using namespace std;
template <class T = long long>
struct WeightedUnionFind
{
public:
WeightedUnionFind() : _n(0) {}
explicit WeightedUnionFind(int n, T e = 0) : _n(n), parent_or_size(n, -1), diff_weight(n, e) {}
int merge(int a, int b, T w)
{
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
assert(valid(a, b, w));
int x = leader(a), y = leader(b);
if (same(a, b))
{
return x;
}
w += weight(a), w -= weight(b);
if (x == y)
{
return x;
}
if (-parent_or_size[x] < -parent_or_size[y])
{
swap(x, y), w *= -1;
}
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
diff_weight[y] = w;
return x;
}
bool same(int a, int b)
{
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
bool valid(int a, int b, T w)
{
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return !same(a, b) || diff(a, b) == w;
}
int leader(int a)
{
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0)
{
return a;
}
int r = leader(parent_or_size[a]);
diff_weight[a] += diff_weight[parent_or_size[a]];
return parent_or_size[a] = r;
}
int size(int a)
{
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
T weight(int a)
{
assert(0 <= a && a < _n);
leader(a);
return diff_weight[a];
}
T diff(int a, int b)
{
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
assert(same(a, b));
return weight(b) - weight(a);
}
vector<vector<int>> groups()
{
vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++)
{
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
vector<vector<int>> result(_n);
for (int i = 0; i < _n; i++)
{
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++)
{
result[leader_buf[i]].push_back(i);
}
result.erase(
remove_if(result.begin(), result.end(),
[&](const vector<int> &v)
{ return v.empty(); }),
result.end());
return result;
}
private:
int _n;
vector<int> parent_or_size;
vector<T> diff_weight;
};
#line 5 "test/DataStructure/weighted_union_find/yosupo-unionfind_with_potential.cpp"
#include <atcoder/all>
using namespace std;
int main()
{
int N, Q;
cin >> N >> Q;
WeightedUnionFind<atcoder::modint998244353> wuf(N);
for (int i = 0; i < Q; i++)
{
int t;
cin >> t;
if (t == 0)
{
int u, v, x;
cin >> u >> v >> x;
if (wuf.valid(u, v, x))
{
wuf.merge(u, v, x);
}
cout << wuf.valid(u, v, x) << endl;
}
if (t == 1)
{
int x, y;
cin >> x >> y;
if (!wuf.same(x, y))
{
cout << "-1" << endl;
}
else
{
cout << wuf.diff(x, y).val() << endl;
}
}
}
return 0;
}
test/DataStructure/weighted_union_find/yosupo-unionfind_with_potential.cpp