この問題は，非連結であるような頂点のペアの集合を直接管理するのではなく，「非連結である可能性がある頂点のペアの集合」を考えることで解きやすくなります．

距離が最小であるような頂点対を高速に取得できる優先度付きキュー \(Q\) を用意します．はじめ，頂点対 \((u,v)\ (1\leq u\lt v\leq N)\) をすべて \(Q\) に追加しておきます．また，サイズが \(N+Q\) の Union-Find を用意し，頂点の連結性を高速に判定できるようにします．

クエリ \(1\) では，\(Q\) に \((1,n), (2, n), \ldots, (n-1,n)\) を追加します．

クエリ \(2\) では， \(Q\) が空でない限り以下の操作を行います．

• 距離が最小であるような \((u,v)\in Q\) を取り出す．
  • 頂点 \(u,v\) が連結であれば何もしない．
  • そうでないとき，Union-Find で \(u,v\) を連結にする．\(k=d(u,v)\) として，\(Q\) の距離が最小である頂点対 \((u',v')\) が \(k\) と等しい限り，それを取り出してUnion-Find で \(u',v'\) を連結にする．この処理が終わった後，\(k\) を出力して，操作を終了する．

クエリ \(2\) で何も出力されなかった場合，\(G\) の連結成分は \(1\) であるため，-1 を出力します．

クエリ \(3\) では，頂点 \(u,v\) が連結かどうかを Union-Find で判定します．

計算量について，\(Q\) に追加される頂点対は \(O((N+Q)^2)\) 個あるためこれがボトルネックとなり，計算量は \(O((N+Q)^2\log(N+Q))\) です．

実装例(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;
    }
  }
}