DSU GRAF BIPARTIT

struct DSU {
  vector<int> p, par, r;
  /// par - paritatea distantei de la nod la lider
  /// daca doua noduri au 'par' egal au aceeasi culoare
  /// daca se adauga o muchie intre 2 noduri cu aceeasi culoare si acelasi lider, atunci se obtine un ciclu de lungime impara, iar graful nu mai este bipartit

  DSU(int N) {
    p.resize(N + 1);
    iota(p.begin(), p.end(), 0);
    par.resize(N + 1);
    r.assign(N + 1, 1);
  }

  pair<int,int> get(int x) {
    if (x == p[x])
      return {x, 0};
    pair<int,int> root = get(p[x]);
    p[x] = root.first;
    par[x] ^= root.second;
    return {p[x], par[x]};
  }

  void unite(int u, int v) {
    pair<int,int> x = get(u), y = get(v);
    if (r[x.first] > r[y.first])
      swap(x, y);
    p[x.first] = y.first;
    par[x.first] = (x.second + y.second + 1) & 1;
    r[y.first] += r[x.first];
  }
};