#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i, n) for (int (i) = 0; (i) < (n); (i)++) #define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++) #define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--) #define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--) #define DEBUG(C) cerr << #C << " = " << C << endl; using LL = long long; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; using VD = vector; using VVD = vector; using PII = pair; using PDD = pair; using PLL = pair; using VPII = vector; template using VT = vector; #define ALL(a) begin((a)), end((a)) #define RALL(a) rbegin((a)), rend((a)) #define SORT(a) sort(ALL((a))) #define RSORT(a) sort(RALL((a))) #define REVERSE(a) reverse(ALL((a))) #define MP make_pair #define FORE(a, b) for (auto &&a : (b)) #define FIND(s, e) ((s).find(e) != (s).end()) #define EB emplace_back template inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;} template inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;} const int INF = 1e9; const int MOD = INF + 7; const LL LLINF = 1e18; class StronglyConnectedComponentDecomposition { private: std::vector used; std::vector> graph, revgraph; std::vector comp; std::vector sortNode; void dfs(int now) { this->used[now] = true; for (const int e : this->graph[now]) { if (!this->used[e]) dfs(e); } this->sortNode.emplace_back(now); return; } void dfs2(int now, int cnt) { this->used[now] = true; for (const int e : this->revgraph[now]) { if (!this->used[e]) dfs2(e, cnt); } this->comp[now] = cnt; return; } public: StronglyConnectedComponentDecomposition() {} StronglyConnectedComponentDecomposition(const int n) : used(n, false), graph(n), revgraph(n), comp(n, 0) {} void resize(const int n) { this->used.resize(n, false); this->graph.resize(n); this->revgraph.resize(n); this->comp.resize(n, 0); } void addEdge(const int from, const int to) { this->graph[from].emplace_back(to); this->revgraph[to].emplace_back(from); return; } int solve() { std::fill(std::begin(this->used), std::end(this->used), false); for (int i = 0; i < (int)this->used.size(); i++) { if (!used[i]) dfs(i); } std::fill(std::begin(this->used), std::end(this->used), false); std::reverse(std::begin(this->sortNode), std::end(this->sortNode)); int res = 0; for (const int n : this->sortNode) { if (!this->used[n]) dfs2(n, res++); } return res; } std::vector getComp() { return this->comp; } bool same(const int a, const int b) { return this->comp[a] == this->comp[b]; } }; // need SCC Library!!!! class Two_Sat { private: StronglyConnectedComponentDecomposition scc; int sz; public: Two_Sat(const int n) : scc(n * 2), sz(n) {} Two_Sat() {} // add (a OR b) void addLogic(const int a, const bool ab, const int b, const bool bb) { this->scc.addEdge(a + (ab ? 0 : this->sz), b + (bb ? 0 : this->sz)); this->scc.addEdge(b + (bb ? 0 : this->sz), a + (ab ? 0 : this->sz)); } // (logic 1) AND (logic 2) AND ... (logic N) <- satisfy bool calcSatisfy() { this->scc.solve(); for (int i = 0; i < this->sz; i++) { if (this->scc.same(i, i + this->sz)) return false; } return true; } }; const int MAX = 2010; int N, M; pair lr[MAX][2]; bool check(const pair &p1, const pair &p2) { bool res = false; res |= p2.first <= p1.first && p1.first <= p2.second; res |= p2.first <= p1.second && p1.second <= p2.second; res |= p1.first <= p2.first && p2.first <= p1.second; res |= p1.first <= p2.second && p2.second <= p1.second; return res; } int main(void) { cin >> N >> M; Two_Sat ts(N); for (int i = 0; i < N; i++) { int l, r; cin >> l >> r; lr[i][0] = make_pair(l - 1, r - 1); lr[i][1] = make_pair(M - l, M - r); } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i != j) { for (int k = 0; k < 2; k++) { for (int l = 0; l < 2; l++) { if (check(lr[i][k], lr[j][l])) { ts.addLogic(i, k, j, l); } } } } } } puts(ts.calcSatisfy() ? "YES" : "NO"); }