//#define _GLIBCXX_DEBUG #include #define rep(i, n) for(int i=0; i; using vs = vector; using vi = vector; using vvi = vector; template using PQ = priority_queue; template using PQG = priority_queue, greater >; const int INF = 0xccccccc; const ll LINF = 0xcccccccccccccccLL; template inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);} template inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);} template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second;} template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second;} struct SCC { struct csr { vector start, elist; csr(int n, const vector> &edges) : start(n+1), elist(edges.size()) { for(pair e:edges) { start[e.first+1]++; } for(int i = 1; i <= n; i++) { start[i] += start[i-1]; } vector counter = start; for(pair e:edges) { elist[counter[e.first]++] = e.second; } } }; int n; vector> edges; SCC(int n_) : n(n_) {} void add(int from, int to) {edges.emplace_back(from, to);} pair> scc_ids() { csr g(n, edges); int now_ord = 0, group_num = 0; vector used, low(n), ord(n, -1), ids(n); used.reserve(n); auto dfs = [&](auto self, int v)->void { low[v] = ord[v] = now_ord++; used.push_back(v); for(int i = g.start[v]; i < g.start[v+1]; i++) { int to = g.elist[i]; if(ord[to] == -1) { self(self, to); low[v] = min(low[v], low[to]); } else { low[v] = min(low[v], ord[to]); } } if(low[v] == ord[v]) { while(true) { int u = used.back(); used.pop_back(); ord[u] = n; ids[u] = group_num; if(u == v) break; } group_num++; } }; for(int i = 0; i < n; i++) { if(ord[i] == -1) dfs(dfs, i); } for(int &x:ids) { x = group_num - 1 - x; } return {group_num, ids}; } vector> scc() { pair> ids = scc_ids(); int group_num = ids.first; vector counts(group_num); for(int x:ids.second) counts[x]++; vector> groups(group_num); for(int i = 0; i < group_num; i++) { groups[i].reserve(counts[i]); } for(int i = 0; i < n; i++) { groups[ids.second[i]].push_back(i); } return groups; } }; //SCC is needed struct two_sat { int n; vector boolean_val; SCC scc; two_sat():n(0), scc(0) {} two_sat(int n_):n(n_), boolean_val(n_), scc(n_<<1) {} void add(int i, bool ii, int j, bool jj) { scc.add(i + (ii?0:n), j + (jj?n:0)); scc.add(j + (jj?0:n), i + (ii?n:0)); } bool satisfiable() { vector id = scc.scc_ids().second; for(int i = 0; i < n; i++) { if(id[i] == id[i+n]) return false; boolean_val[i] = id[i] < id[i+n]; } return true; } }; template struct SegTreeL { using FX = function; using FA = function; using FF = function; int n; FX fx; FA fa; FF ff; const S es; const F ef; vector dat; vector laz; SegTreeL(int n_, FX fx_, FA fa_, FF ff_, S es_, F ef_) : fx(fx_), fa(fa_), ff(ff_), es(es_), ef(ef_) { n = 1; while(n_ > n) n <<= 1; dat.assign(n*2-1, es); laz.assign(n*2-1, ef); } inline int chld(int k) {return k*2+1;} inline int chrd(int k) {return k*2+2;} void set(int i, S s) {dat[i+n-1] = s;} void build() { for(int k = n-2; k >= 0; k--) dat[k] = fx(dat[chld(k)], dat[chrd(k)]); } void eval(int k) { if(laz[k] == ef) return; if(k < n-1) { laz[chld(k)] = ff(laz[chld(k)], laz[k]); laz[chrd(k)] = ff(laz[chrd(k)], laz[k]); } dat[k] = fa(dat[k], laz[k]); laz[k] = ef; } void update(int a, int b, F x, int k, int l, int r) { eval(k); if(a <= l and r <= b) { laz[k] = ff(laz[k], x); eval(k); } else if(a < r and l < b) { update(a, b, x, chld(k), l, (l+r)>>1); update(a, b, x, chrd(k), (l+r)>>1, r); dat[k] = fx(dat[chld(k)], dat[chrd(k)]); } } void update(int a, int b, F x) {update(a, b, x, 0, 0, n);} S query(int a, int b, int k, int l, int r) { eval(k); if(r <= a or b <= l) return es; else if(a <= l and r <= b) return dat[k]; else { S vl = query(a, b, chld(k), l, (l+r)>>1); S vr = query(a, b, chrd(k), (l+r)>>1, r); return fx(vl, vr); } } S query(int a, int b) {return query(a, b, 0, 0, n);} //debug inline const S operator[](const int i) {return query(i, i+1);} void print() {for(int i = 0; i < n; i++) cout << (*this)[i] << (i == n-1?'\n':' ');} }; #define M 4010 //head int n, m; vi pink[M]; bitset check; auto fx = [](set a, set b)->set { set res; set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(res, res.end())); return res; }; SegTreeL, set> rng(M>>1, fx, fx, fx, set(), set()); int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; two_sat TS(n); rep(i, n) { check = 0; int l, r; cin >> l >> r; set u = rng.query(l, r+1); for(int x:u) { if(x >= n) { TS.add(i, false, x-n, true); } else { TS.add(i, false, x, false); } } u = rng.query(m-1-r, m-l); for(int x:u) { if(x >= n) { TS.add(i, true, x-n, true); } else { TS.add(i, true, x, false); } } rng.update(l, r+1, set({i})); rng.update(m-1-r, m-l, set({i+n})); } cout << (TS.satisfiable()?"YES\n":"NO\n"); }