#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,s,n) for(int i = (s); (n) > i; i++) #define REP(i,n) rep(i,0,n) #define RANGE(x,a,b) ((a) <= (x) && (x) <= (b)) #define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b)) #define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d)) #define PW(x) ((x)*(x)) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define MODU 1000000007 #define bitcheck(a,b) ((a >> b) & 1) #define bitset(a,b) ( a |= (1 << b)) #define bitunset(a,b) (a &= ~(1 << b)) #define MP(a,b) make_pair((a),(b)) #define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second)) #define pritnf printf #define scnaf scanf #define itn int #define PI 3.141592653589 #define izryt bool using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; template void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); } pii Dir[8] = { //移動 { 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 }, { 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 } }; class Graph { public: int vn; int sumcost = 0; vector> g; Graph(int n) { vn = n; g.resize(n); } virtual void con(int a, int b, int w) = 0; int getWeight(int f, int t) { auto itr = lower_bound(ALL(g[f]), make_pair(t, INT_MIN)); if (itr != g[f].end()) return itr->second; return INT_MIN; } int Costsum() { return sumcost; } }; class BiDGraph : public Graph {//無向 public: BiDGraph(int n) : Graph(n) {} void con(int a, int b, int w = 1) { g[a].push_back({ b,w }); g[b].push_back({ a, w }); sumcost++; } }; class DGraph : public Graph {//有向 public: DGraph(int n) : Graph(n) {} void con(int a, int b, int w = 1) { g[a].push_back({ b,w }); sumcost++; } }; void SCC(DGraph& g, vector& scc) { vector orb(g.vn, -1); scc.resize(g.vn, -1); int cc = 0; int k = 0; vector used(g.vn); stack st; function dfs = [&](int cur) { int low = orb[cur] = ++k; st.push(cur); used[cur] = 1; for (auto itr : g.g[cur]) { if (orb[itr.first] == -1) low = min(low, dfs(itr.first)); else if (used[itr.first]) low = min(low, orb[itr.first]); } if (low == orb[cur]) { while (1) { int cp = st.top(); st.pop(); used[cp] = 0; scc[cp] = cc; if (cp == cur) break; } cc++; } return low; }; REP(i, g.vn) if (orb[i] < 0) dfs(i); } bool TWO_SAT(int n, vector clause) {//否定は-, 1-indexed DGraph g(n * 2); for (auto itr : clause) { int a = (itr.first < 0 ? -itr.first+n : itr.first)-1, b = (itr.second < 0 ? -itr.second+ n : itr.second)-1; g.con(a + (a>=n?-n:n),b); g.con(b + (b >= n ? -n : n),a); } vector scc; SCC(g, scc); REP(i, n) { if (scc[i] == scc[i + n]) { return 0; } } return 1; } signed main() { int n, m; scanf("%d %d", &n, &m); vector wall(n); REP(i,n){ scanf("%d %d", &wall[i].first, &wall[i].second); } vector clause; for (int i = 0; n * 2 > i; i += 2) { clause.push_back({ -(i + 1), -(i + 2) }); clause.push_back({ (i + 1), (i + 2) }); pii ti = wall[i/2]; REP(ci, 2) { for (int j = i + 2; n * 2 > j; j += 2) { pii tj = wall[j/2]; REP(cj, 2) { if (DUPLE(ti.first, ti.second, tj.first, tj.second)) { clause.push_back({ -(i + ci + 1), -(j + cj + 1) }); } tj = { m - wall[j/2].second - 1,m - wall[j/2].first - 1 }; } } ti = { m - wall[i/2].second - 1,m - wall[i/2].first - 1 }; } } printf("%s\n", TWO_SAT(n*2, clause) ? "YES" : "NO"); return 0; }