#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include "collapse.h"

using namespace std;
using Pii = pair<int, int>; 

const int N = 1e5 + 5, B = 333;

int n, m, q;
int fa[N], p[N];
set<Pii> es;
map<Pii, int> mp;

struct E {
  int x, y, l, r;

  // One edge connected x and y with time [l, r]
}; 

struct Q {
  int t, p, id;
}; 

struct Union_find {
  int fa[N], d[N]; 
  vector<Pii> v; 

  void Init () {
    iota(fa + 1, fa + n + 1, 1);
    fill(d + 1, d + n + 1, 0);
    v.clear();
  }

  int Find (int x) {
    return fa[x] == x ? x : Find(fa[x]);
  } 

  void Unite (int x, int y) {
    x = Find(x), y = Find(y);
    if (d[x] < d[y]) swap(x, y);
    v.push_back({y, d[x]});
    fa[y] = x; 
    d[x] = max(d[x], d[y] + 1);
  }

  bool Try_to_unite (int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return 0;  
    Unite(x, y); 
    return 1;
  }

  int Get_time () {
    return v.size();
  }

  void Roll_back (int t) {
    while (v.size() > t) {
      Pii t = v.back();
      v.pop_back();
      d[fa[t.first]] = t.second;
      fa[t.first] = t.first;
    }
  }
} uf;

vector<E> ev; 

int Find (int x) {
  if (fa[x] == x) return x;
  return fa[x] = Find(fa[x]);
} 

vector<int> simulateCollapse (int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
  [&]() -> void {
    // Remake
    n = N, m = T.size(), q = W.size();
    for (auto &x : X) ++x;
    for (auto &y : Y) ++y; 
    for (auto &w : W) ++w;
    for (auto &p : P) ++p;
    for (int i = 0; i < m; ++i) {
      if (X[i] > Y[i]) 
        swap(X[i], Y[i]);
    }
    for (int i = 0; i < m; ++i) {
      int x = X[i], y = Y[i];
      if (!T[i]) {
        mp.insert({{x, y}, i + 1});
      }
      else {
        auto it = mp.find({x, y});
        ev.push_back(E({x, y, it->second, i}));
        mp.erase(it);
      }
    }
    for (auto i : mp) {
      ev.push_back(E({i.first.first, i.first.second, i.second, m})); 
    }
    
    // cout << "Edge set : " << '\n';
    // for (auto i : ev) {
    //   cout << i.x << ' ' << i.y << ' ' << i.l << ' ' << i.r << '\n';
    // }
    // cout << "-------------" << '\n';
    // exit(0);
  }();
  iota(p, p + q, 0);
  sort(p, p + q, [&](int i, int j) -> bool {
    return W[i] < W[j];
  });
  vector<int> ans(q);
  for (int tl = 0, tr; tl < q; tl = tr + 1) {
    tr = min(tl + B - 1, q - 1);
    int L = W[p[tl]], R = W[p[tr]];
    vector<Pii> cover;
    vector<E> vec; 
    for (auto e : ev) {
      if (e.l <= L && e.r >= R) {
        cover.push_back({e.x, e.y});
      }
      else if (R >= e.l && e.r >= L) {
        vec.push_back(e);
      }
    }
    sort(cover.begin(), cover.end(), [&](Pii a, Pii b) -> bool {
      return a.second < b.second;
    });
    vector<Q> qv;
    for (int i = tl; i <= tr; ++i) {
      int id = p[i];
      qv.push_back(Q({W[id], P[id], id}));
    }
    sort(qv.begin(), qv.end(), [&](Q a, Q b) -> bool {
      return a.p < b.p;
    });
    auto cur = cover.begin();
    uf.Init();
    int ucnt = 0;
    // The times of successful merge
    for (auto q : qv) {
      int p = q.p, t = q.t, id = q.id;
      while (cur != cover.end() && cur->second <= p) {
        ucnt += uf.Try_to_unite(cur->first, cur->second);
        ++cur;
      }
      int timel = uf.Get_time(), tmpcnt = 0; 
      for (auto e : vec) {
        if (e.l <= t && e.r >= t && e.y <= p) {
          tmpcnt += uf.Try_to_unite(e.x, e.y);
        }
      }
      ans[q.id] += p - ucnt - tmpcnt;
      uf.Roll_back(timel);
    }
    reverse(qv.begin(), qv.end());
    sort(cover.begin(), cover.end(), [&](Pii a, Pii b) -> bool {
      return a.first > b.first;
    });
    cur = cover.begin();
    uf.Init();
    ucnt = 0; 
    for (auto q : qv) {
      int p = q.p, t = q.t, id = q.id;
      while (cur != cover.end() && cur->first > p) {
        ucnt += uf.Try_to_unite(cur->first, cur->second);
        ++cur;
      }
      int timel = uf.Get_time(), tmpcnt = 0;
      for (auto e : vec) {
        if (e.l <= t && e.r >= t && e.x > p) {
          tmpcnt += uf.Try_to_unite(e.x, e.y);
        }
      }
      ans[q.id] += (n - p) - ucnt - tmpcnt;
      uf.Roll_back(timel);
    }
  }
  return ans;
}

// void Test () {
//   int N, C, Q;
//   cin >> N >> C >> Q;
//   vector<int> T, X, Y;
//   for (int i = 0, t, x, y; i < C; ++i) {
//     cin >> t >> x >> y;
//     T.push_back(t), X.push_back(x), Y.push_back(y);
//   }
//   vector<int> W, P;
//   for (int i = 0, w, p; i < Q; ++i) {
//     cin >> w >> p;
//     W.push_back(w), P.push_back(p);
//   }
//   vector<int> ans = simulateCollapse(N, T, X, Y, W, P);
//   for (auto i : ans) {
//     cout << i << '\n';
//   }
// }

// int main () { Test(); }