#pragma GCC optimize "O3" #include using namespace std; using LL=long long; #define FOR(i,l,r) for(int i=(l);i<=(r);++i) #define REP(i,n) FOR(i,0,(n)-1) #define ssize(x) int(x.size()) #ifdef DEBUG auto&operator<<(auto&o,pairp){return o<<"("<p){return o<<"("<(p)<<", "<(p)<<", "<(p)<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<sync_with_stdio(0); int tests; cin >> tests; REP (test, tests) { int n; cin >> n; map> mp; REP (i, n) { int x, y; cin >> x >> y; mp[x + y].emplace_back(y); } mp[LL(3e9)] = vector(); set> t; t.emplace(0, 0, 1); LL last = 0; bool broken = false; for (auto [tm, v] : mp) { if (broken) break; debug(t); while (last < tm) { if (t.empty()) { last = tm; break; } if (broken) break; ++last; map g; for (auto [l, r, w] : t) { g[l] += w - 1; g[l + 1] += w - 1; g[r + 1] -= w - 1; g[r + 2] -= w - 1; } int prv = 0, cur = 0; set> s; for (auto [y, w] : g) { if (!w) continue; if (cur) { s.emplace(prv, y - 1, cur); if (cur > 3) { broken = true; } } cur += w; prv = y; } assert(cur == 0); t = s; debug(last, t); int last_r = -2; int last_w = 0; for (auto [l, r, w] : t) { if (last_r + 1 == l) { if ((w == 2 && last_w == 3) || (last_w == 2 && w == 3)) { broken = true; } } last_r = r; last_w = w; } if (broken) break; } debug(v); for (auto y : v) { debug(y); auto ptr = t.lower_bound(tuple(y + 1, 0, 0)); if (ptr == t.begin()) continue; --ptr; auto [l, r, w] = *ptr; debug(l, r, w); if (l <= y && y <= r) { assert(w); if (w >= 3) { broken = true; break; } t.erase(ptr); if (l < y) t.emplace(tuple(l, y - 1, w)); t.emplace(tuple(y, y, w + 1)); if (y < r) t.emplace(tuple(y + 1, r, w)); } debug(t); if (broken) break; } debug("after", t); } if (broken) { cout << "NO\n"; } else { cout << "YES\n"; } } } /* [t]: {(0, 0, 1)}; [v]: {0}; [y]: 0; [l, r, w]: 0; 0; 1; [t]: {(0, 0, 2)}; ["after", t]: after; {(0, 0, 2)}; [t]: {(0, 0, 2)}; [last, t]: 1; {(0, 1, 1)}; [v]: {1,0}; [y]: 1; [l, r, w]: 0; 1; 1; [t]: {(0, 0, 1),(1, 1, 2)}; [y]: 0; [l, r, w]: 0; 0; 1; [t]: {(0, 0, 2),(1, 1, 2)}; ["after", t]: after; {(0, 0, 2),(1, 1, 2)}; [t]: {(0, 0, 2),(1, 1, 2)}; [last, t]: 2; {(0, 0, 1),(1, 1, 2),(2, 2, 1)}; [v]: {2,1}; [y]: 2; [l, r, w]: 2; 2; 1; [t]: {(0, 0, 1),(1, 1, 2),(2, 2, 2)}; [y]: 1; [l, r, w]: 1; 1; 2; [t]: {(0, 0, 1),(1, 1, 3),(2, 2, 2)}; ["after", t]: after; {(0, 0, 1),(1, 1, 3),(2, 2, 2)}; [t]: {(0, 0, 1),(1, 1, 3),(2, 2, 2)}; [last, t]: 3; {(1, 1, 2),(2, 2, 3),(3, 3, 1)}; [v]: {0}; [y]: 0; ["after", t]: after; {(1, 1, 2),(2, 2, 3),(3, 3, 1)}; [t]: {(1, 1, 2),(2, 2, 3),(3, 3, 1)}; [last, t]: 4; {(1, 1, 1),(2, 2, 3),(3, 3, 2)}; [last, t]: 5; {(2, 2, 2),(3, 3, 3),(4, 4, 1)}; [last, t]: 6; {(2, 2, 1),(3, 3, 3),(4, 4, 2)}; [last, t]: 7; {(3, 3, 2),(4, 4, 3),(5, 5, 1)}; [last, t]: 8; {(3, 3, 1),(4, 4, 3),(5, 5, 2)}; [last, t]: 9; {(4, 4, 2),(5, 5, 3),(6, 6, 1)}; [last, t]: 10; {(4, 4, 1),(5, 5, 3),(6, 6, 2)}; [last, t]: 11; {(5, 5, 2),(6, 6, 3),(7, 7, 1)}; [last, t]: 12; {(5, 5, 1),(6, 6, 3),(7, 7, 2)}; [last, t]: 13; {(6, 6, 2),(7, 7, 3),(8, 8, 1)}; [last, t]: 14; {(6, 6, 1),(7, 7, 3),(8, 8, 2)}; [last, t]: 15; {(7, 7, 2),(8, 8, 3),(9, 9, 1)}; [last, t]: 16; {(7, 7, 1),(8, 8, 3),(9, 9, 2)}; [last, t]: 17; {(8, 8, 2),(9, 9, 3),(10, 10, 1)}; [last, t]: 18; {(8, 8, 1),(9, 9, 3),(10, 10, 2)}; [last, t]: 19; {(9, 9, 2),(10, 10, 3),(11, 11, 1)}; [last, t]: 20; {(9, 9, 1),(10, 10, 3),(11, 11, 2)}; [last, t]: 21; {(10, 10, 2),(11, 11, 3),(12, 12, 1)}; [last, t]: 22; {(10, 10, 1),(11, 11, 3),(12, 12, 2)}; [last, t]: 23; {(11, 11, 2),(12, 12, 3),(13, 13, 1)}; [last, t]: 24; {(11, 11, 1),(12, 12, 3),(13, 13, 2)}; [last, t]: 25; {(12, 12, 2),(13, 13, 3),(14, 14, 1)} */