#include using namespace std; #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double using namespace std; //変数は1-index class SAT_2{ public: SAT_2(int aN) { init(aN); } //変数の数 void init(int aN) { N = aN; VecSize = 2 * N + 1; Edge.resize(VecSize); rEdge.resize(VecSize); used.resize(VecSize); vs.clear(); cmp.resize(VecSize); } //節を登録 void reg(int l, int r) { int tmpL = l, tmpR = r; tmpL *= -1; tmpL += N, tmpR += N; Edge[tmpL].push_back(tmpR); rEdge[tmpR].push_back(tmpL); tmpL = r, tmpR = l; tmpL *= -1; tmpL += N, tmpR += N; Edge[tmpL].push_back(tmpR); rEdge[tmpR].push_back(tmpL); } void dfs(int v) { used[v] = true; for (int i = 0; i < Edge[v].size(); i++) { if(!used[Edge[v][i]]){ dfs(Edge[v][i]); } } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for (int i = 0; i < rEdge[v].size(); i++) { if(!used[rEdge[v][i]]){ rdfs(rEdge[v][i], k); } } } int scc() { for (int i = 0; i < used.size(); i++) { used[i] = false; } vs.clear(); for (int i = 0; i < VecSize; i++) { if(!used[i]) dfs(i); } for (int i = 0; i < used.size(); i++) { used[i] = false; } int k = 0; for (int i = vs.size()-1; 0 <= i; i--) { if(!used[vs[i]]){ rdfs(vs[i], k++); } } return k; } bool checkSatisfy() { scc(); for(int i = 0; i < N; i++){ if(cmp[i] == cmp[i+N+1]){ return false; } } return true; } private: vector> Edge; vector> rEdge; vector used; vector vs; //帰りがけ順の並び vector cmp; //属する連結成分のトポロジカル順序 int N; int VecSize; }; #define MAX_N 2005 #define MAX_M 4005 int N, M; int L[MAX_N], R[MAX_N]; //衝突しているか bool checkCollision(int l1, int r1, int l2, int r2) { if(r1 < l1){ swap(l1, r1); } if(r2 < l2){ swap(l2, r2); } if(l1 <= l2 && l2 <= r1){ return true; } if(l1 <= r2 && r2 <= r1){ return true; } return false; } int main() { cin >> N >> M; for (int i = 1; i <= N; i++) { cin >> L[i] >> R[i]; } SAT_2 sat(N); for (int i = 1; i <= N; i++) { for (int j = i+1; j <= N; j++) { if(i == j){ continue; } if(checkCollision(L[i], R[i], L[j], R[j])){ sat.reg(i, j); } if(checkCollision(L[i], R[i], M - 1 - L[j], M - 1 - R[j])){ sat.reg(i, -j); } if(checkCollision(M - 1 - L[i], M - 1 - R[i], L[j], R[j])){ sat.reg(-i, j); } if(checkCollision(M - 1 - L[i], M - 1 - R[i], M - 1 - L[j], M - 1 - R[j])){ sat.reg(-i, -j); } } } if(sat.checkSatisfy()){ cout << "YES" << endl; } else{ cout << "NO" << endl; } return 0; }