#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#include <vector>
#include "Mylib/DataStructure/UnionFind/persistent_unionfind.cpp"
#include "Mylib/IO/input_tuples_with_index.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
std::vector<hl::persistent_unionfind> G(Q + 1);
G[0] = hl::persistent_unionfind(N);
for (auto [i, t, k, u, v] : hl::input_tuples_with_index<int, int, int, int>(Q)) {
++k;
++i;
if (t == 0) {
G[i] = G[k].merge(u, v);
} else {
std::cout << G[k].is_same(u, v) << "\n";
}
}
return 0;
}
#line 1 "test/yosupo-judge/persistent_unionfind/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#include <vector>
#line 3 "Mylib/DataStructure/Array/persistent_array.cpp"
#include <memory>
#line 5 "Mylib/DataStructure/Array/persistent_array.cpp"
namespace haar_lib {
template <typename T>
class persistent_array {
public:
using value_type = T;
private:
struct node {
bool is_terminal;
int size = 1;
node *left = nullptr, *right = nullptr;
std::unique_ptr<T> value;
node() : is_terminal(false) {}
node(T v) : is_terminal(true), value(new T(v)) {}
};
size_t size_;
int depth_;
node *root_ = nullptr;
int get_size(node *t) const {
return t ? t->size : 0;
}
node *init(int s, int d) {
if (s == 0) return nullptr;
if (d == depth_) {
return new node(T());
} else {
node *t = new node();
t->left = init(s / 2, d + 1);
t->right = init(s - s / 2, d + 1);
t->size = get_size(t->left) + get_size(t->right);
return t;
}
}
void apply_init(node *t, const std::vector<T> &ret, int &i) {
if (not t) return;
if (t->is_terminal) {
*(t->value) = ret[i];
++i;
return;
}
apply_init(t->left, ret, i);
apply_init(t->right, ret, i);
}
persistent_array(node *root) : root_(root) {}
void calc_depth() {
depth_ = 1;
while ((int) size_ > (1 << depth_)) depth_ += 1;
depth_ += 1;
}
public:
persistent_array() {}
persistent_array(size_t size) : size_(size) {
calc_depth();
root_ = init(size_, 1);
}
persistent_array(const std::vector<T> &v) : size_(v.size()) {
calc_depth();
root_ = init(size_, 1);
int i = 0;
apply_init(root_, v, i);
}
persistent_array(const persistent_array &v) {
this->root_ = v.root_;
this->size_ = v.size_;
this->depth_ = v.depth_;
}
protected:
T get(node *t, int i) const {
if (t->is_terminal) return *(t->value);
int k = get_size(t->left);
if (i < k)
return get(t->left, i);
else
return get(t->right, i - k);
}
public:
T operator[](int i) const {
return get(root_, i);
}
protected:
node *set(node *prev, int i, const T &val) const {
if (prev->is_terminal) return new node(val);
int k = get_size(prev->left);
node *t = new node();
if (i < k) {
t->right = prev->right;
t->left = set(prev->left, i, val);
t->size = get_size(t->right) + get_size(t->left);
} else {
t->left = prev->left;
t->right = set(prev->right, i - k, val);
t->size = get_size(t->right) + get_size(t->left);
}
return t;
}
public:
persistent_array set(int i, const T &val) const {
node *ret = set(root_, i, val);
return persistent_array(ret);
}
protected:
void traverse(node *t, std::vector<T> &ret) const {
if (not t) return;
if (t->is_terminal) {
ret.push_back(*(t->value));
return;
}
traverse(t->left, ret);
traverse(t->right, ret);
}
public:
std::vector<T> data() const {
std::vector<T> ret;
traverse(root_, ret);
return ret;
}
};
} // namespace haar_lib
#line 4 "Mylib/DataStructure/UnionFind/persistent_unionfind.cpp"
namespace haar_lib {
class persistent_unionfind {
persistent_array<int> par_;
persistent_unionfind(persistent_array<int> par) : par_(par) {}
public:
persistent_unionfind() {}
persistent_unionfind(int n) : par_(persistent_array<int>(std::vector<int>(n, -1))) {}
int root_of(int i) const {
const int p = par_[i];
if (p < 0) return i;
return root_of(p);
}
bool is_same(int i, int j) const {
return root_of(i) == root_of(j);
}
int size_of(int i) const {
return -par_[root_of(i)];
}
persistent_unionfind merge(int i, int j) const {
const int ri = root_of(i), rj = root_of(j);
if (ri == rj) return *this;
const int size_i = -par_[ri];
const int size_j = -par_[rj];
persistent_array<int> ret = par_;
if (size_i > size_j) {
ret = ret.set(ri, -(size_i + size_j));
ret = ret.set(rj, ri);
} else {
ret = ret.set(rj, -(size_i + size_j));
ret = ret.set(ri, rj);
}
return persistent_unionfind(ret);
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples_with_index.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples_with_index.cpp"
#include <tuple>
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples_with_index.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuplesWithIndex {
struct iter {
using value_type = std::tuple<int, Args...>;
value_type value;
bool fetched = false;
int N;
int c = 0;
value_type operator*() {
if (not fetched) {
std::tuple<Args...> temp;
std::cin >> temp;
value = std::tuple_cat(std::make_tuple(c), temp);
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuplesWithIndex(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples_with_index(int N) {
return InputTuplesWithIndex<Args...>(N);
}
} // namespace haar_lib
#line 7 "test/yosupo-judge/persistent_unionfind/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
std::vector<hl::persistent_unionfind> G(Q + 1);
G[0] = hl::persistent_unionfind(N);
for (auto [i, t, k, u, v] : hl::input_tuples_with_index<int, int, int, int>(Q)) {
++k;
++i;
if (t == 0) {
G[i] = G[k].merge(u, v);
} else {
std::cout << G[k].is_same(u, v) << "\n";
}
}
return 0;
}