This problem can be made easier to solve by, instead of managing the set of pairs of vertices that are disconnected, the pairs that “might” be disconnected.

Prepare a priority queue \(Q\) so that we can retrieve a vertex pair with the minimum distance. Initially, put all vertex pairs \((u,v)\ (1\leq u\lt v\leq N)\) to \(Q\). Also, prepare a Disjoint Set Union (DSU) of size \(N+Q\) so that we can determine the connectivity of vertices fast.

For query \(1\), add \((1,n), (2, n), \ldots, (n-1,n)\) to \(Q\).

For query \(2\), perform the following operation while \(Q\) is not empty.

• Pop \((u,v)\in Q\) with the minimum distance.
  • Do nothing if vertices \(u\) and \(v\) are connected.
  • Otherwise, make \(u\) and \(v\) connected in DSU. Let \(k=d(u,v)\). While the vertex pair \((u',v')\) with the minimum distance in \(Q\) is equal to \(k\), pop that and make \(u'\) and \(v'\) connected in the DSU. After this, print \(k\) and terminate the procedure.

If nothing was printed by query \(2\), then \(G\) has exactly one connected component, so print -1.

For query \(3\), determine if vertices \(u\) and \(v\) are connected using the DSU.

The computational complexity is \(O((N+Q)^2\log(N+Q))\), where the bottle neck is inserting \(O((N+Q)^2)\) pairs of vertices inserted to \(Q\).

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

using S = pair<int, int>;

#include <atcoder/dsu>
using namespace atcoder;

int d(S p, S q) { return abs(p.first - q.first) + abs(p.second - q.second); }

int main() {
  int N, Q;
  cin >> N >> Q;

  vector<S> xy;
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    xy.push_back({x, y});
  }

  dsu uf(N + Q);

  using T = array<int, 3>;
  auto cmp = [](const T& a, const T& b) { return a[0] > b[0]; };
  priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);

  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      pq.push({d(xy[i], xy[j]), i, j});
    }
  }

  while (Q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, y;
      cin >> x >> y;
      int n = xy.size();
      xy.push_back({x, y});
      for (int i = 0; i < n; i++) {
        pq.push({d(xy[i], xy[n]), i, n});
      }
    }
    if (t == 2) {
      int ans = -1;
      while (!pq.empty()) {
        auto [mn, u, v] = pq.top();
        pq.pop();
        if (!uf.same(u, v)) {
          ans = mn;
          uf.merge(u, v);
          while (!pq.empty()) {
            auto [mn2, u2, v2] = pq.top();
            if (mn2 != mn) break;
            pq.pop();
            uf.merge(u2, v2);
          }
          break;
        }
      }
      cout << ans << endl;
    }
    if (t == 3) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      cout << (uf.same(u, v) ? "Yes" : "No") << endl;
    }
  }
}