#include using namespace std; #pragma region Macros #define ll long long #define ld long double #define FOR(i,l,r) for(ll i=(l);i<(r);++i) #define REP(i,n) FOR(i,0,n) #define REPS(i,n) FOR(i,1,n+1) #define RFOR(i,l,r) for(ll i=(l);i>=(r);--i) #define RREP(i,n) RFOR(i,n-1,0) #define RREPS(i,n) RFOR(i,n,1) #define pb push_back #define eb emplace_back #define SZ(x) ((ll)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() template using V = vector; template using VV = V>; using P = pair; using Graph = VV; #define ios\ ios::sync_with_stdio(false);\ cin.tie(nullptr); #define VEC(type, name, size)\ V name(size);\ IN(name) #define VVEC(type, name, h, w)\ VV name(h, V(w));\ IN(name) #define INT(...)\ int __VA_ARGS__;\ IN(__VA_ARGS__) #define LL(...)\ ll __VA_ARGS__;\ IN(__VA_ARGS__) #define STR(...)\ string __VA_ARGS__;\ IN(__VA_ARGS__) #define CHAR(...)\ char __VA_ARGS__;\ IN(__VA_ARGS__) #define DOUBLE(...)\ DOUBLE __VA_ARGS__;\ IN(__VA_ARGS__) #define LD(...)\ LD __VA_ARGS__;\ IN(__VA_ARGS__) template void scan(T a) { cin >> a; } void scan(int &a) { cin >> a; } void scan(long long &a) { cin >> a; } void scan(char &a) { cin >> a; } void scan(double &a) { cin >> a; } void scan(long double &a) { cin >> a; } void scan(char a[]) { scanf("%s", a); } void scan(string &a) { cin >> a; } template void scan(V &); template void scan(pair &); template void scan(V &a) { for(auto &i : a) scan(i); } template void scan(pair &p){ scan(p.first); scan(p.second); } template void scan(T &a) { cin >> a; } void IN() {} template void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); } template inline void print(T x){ cout << x << '\n';} template V press(V &x){ V res = x; sort(all(res)); res.erase(unique(all(res)), res.end()); REP(i, SZ(x)){ x[i] = lower_bound(all(res), x[i]) - res.begin(); } return res; } template inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; } template inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; } inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';} inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';} inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}} template inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}} template T Roundup_div(T x, T y) {return (x+(y-1))/y;} template T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; } const ll INF = 1e18; #pragma endregion struct SCC{ const Graph &g; Graph ng, rg; V compo, order, used; //g:元のグラフ, ret:強連結成分分解後のグラフ SCC(Graph &g, Graph &ret) : g(g), ng(SZ(g)), rg(SZ(g)), compo(SZ(g), -1), used(SZ(g)){ REP(i, SZ(g)){ for(auto v : g[i]){ ng[i].pb(v); rg[v].pb(i); } } build(ret); } int operator[](int k){ return compo[k];} void dfs(int now){ if(used[now]) return; used[now] = true; for(auto to : ng[now]) dfs(to); order.eb(now); } void rdfs(int now, int count){ if(compo[now] != -1) return; compo[now] = count; for(auto to : rg[now]) rdfs(to, count); } void build(Graph &ret){ REP(i, SZ(ng)) dfs(i); reverse(rall(order)); int group = 0; for(auto i : order) if(compo[i] == -1) rdfs(i, group), group++; ret.resize(group); REP(i, SZ(g)){ for(auto &to : g[i]){ int s = compo[i], t = compo[to]; if(s != t) ret[s].eb(t); } } } }; struct TwoSat{ int n; Graph g; TwoSat(int n) : n(n), g(n * 2){} int negate(int v){return (n + v) % (n * 2);} void add_if(int u,int v){ //u -> v <=> !v -> !u g[u].pb(v); g[negate(v)].pb(negate(u)); } void add_and(int u, int v){ //u and v <=> u -> v and v -> u add_if(u, v); add_if(v, u); } void add_or(int u,int v){ //u or v <=> !u -> v add_if(negate(u), v); } void add_nand(int u,int v){ //u nand v <=> u -> !v add_if(u, negate(v)); } void set_true(int v){ //v <=> !v -> v g[negate(v)].pb(v); } void set_false(int v){ //!v <=> v -> !v g[v].pb(negate(v)); } vector build(){ Graph ret; SCC scc(g, ret); vector res(n); for(int i=0;i scc[n+i]; } return res; } }; int main(){ INT(n, m); V<> l(n), r(n); REP(i, n) cin >> l[i] >> r[i]; TwoSat TS(n); REP(i, n) REP(j, n){ if(i != j){ // iとjの区間が重なる場合 if(!(r[i] < l[j] or r[j] < l[i])){ TS.add_nand(i, j); TS.add_nand(i + n, j + n); } // iとnotjの区間が重なる場合 if(!(r[i] < m - r[j] - 1 or m - l[j] - 1 < l[i])){ TS.add_nand(i, j + n); } } } V res = TS.build(); YES(SZ(res)); }