We can perform all of the second operations before the first. Using the second operation, we can map any $x$ coordinate present in the input to any $y$ coordinate present in the input. Let $S_x$ denote the multiset of $x$ coordinates and $S_y$ denote the multiset of $y$ coordinates.

Consider an arbitrary multiset $S$. We want to pair $S$ into some number $k$ of "equal" pairs and $n-k$ "diff 1" pairs. $(x,x)$ is considered an equal pair and $(x,x+1)$ is considered a "diff 1" pair. Of course, it's sometimes possible to do this in many different ways, but the only things we're interested in are the minimum number of equal pairs and the maximum number of equal pairs because it turns out that when you have {a, a, a+1, a+1}, you can convert two equal pairs into 2 diff-1 pairs and this makes a difference of 2 so basically you have an interval {min, max} where it's possible to create anywhere between min and max equal pairs (min, min+2, min+4, ...., max-2, max). We can find both min and max with greedy.

We want to find a solution which has $k$ "equal x pairs" and $n-k$ "diff1 x pairs", and $k$ "diff1 y pairs" and $n-k$ "equal y pairs". So if we pair up both $S_x$ and $S_y$ and find their intervals of possibilities, there exists a solution if they intersect.

Aakash Gokhale's code:

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
using vi = vector<int>;
using pi = array<int, 2>;
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define nl '\n'
 
void solve() {
    int n; cin >> n;
    vi x(n), y(n);
    FOR(i, 0, n) cin >> x[i] >> y[i];
    sort(all(x));
    sort(all(y));
    for (int i = 0; i < n; i += 2) {
        if (x[i + 1] - x[i] >= 2
            or y[i + 1] - y[i] >= 2) {
                cout << "NO" << nl;
                return;
            }
    }
    auto get_range = [&] (vi v) -> pi {
        int lo = 0;
        for (int i = 0; i < n; i += 2) {
            lo += v[i] != v[i + 1];
        }
        int hi = 0;
        map<int, int> m;
        FOR(i, 0, n) m[v[i]]++;
        while (m.size()) {
            auto [i, c] = *m.begin();
            if (m.count(i + 1)) {
                int d = min(c, m[i + 1]);
                if ((m[i] - d) & 1) d--;
                m[i + 1] -= d;
                m[i] -= d;
                hi += d;
            }
            m.erase(i);
        }
        return {lo, hi};
    };
    auto [xl, xr] = get_range(x);
    auto [yl, yr] = get_range(y);
    for (int i = xl; i <= xr; i += 2) {
        if (clamp(n / 2 - i, yl, yr) == n / 2 - i) {
            if ((n / 2 - i) % 2 == yl % 2) {
                cout << "YES" << nl;
                return;
            }
        }
    }
    cout << "NO" << nl;
}
 
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t; while (t--) solve();
}