// 下記, ライブラリ を 参照. // https://github.com/RanRanLibrary/Library/commit/662d4e41744468ddf6a8cfac4945c42b1456fe42 #include using namespace std; #define rep(i, n) for(int i = 0; i < (n); i++) typedef vector vi; // 強連結成分分解(Strongly Connected Component). struct SCCGraph: public vector{ // 属する強連結成分の番号(トポロジカル順序になっている) vector order; // 帰りがけ順. vector vs; // すでに調べたか. vector used; // 継承コンストラクタ. using vector::vector; // コピーコンストラクタを使用可能にする. SCCGraph(const vector &v): vector::vector(v) {} // a -> b の辺を追加. void add_edge(int a, int b){ (*this)[a].push_back(b); } // scc()で使う. void dfs(int n, int k, vector &v, vector &rv){ used[n] = true; order[n] = k; for(auto t: v[n]){ // 逆辺のグラフを作成 rv[t].push_back(n); if(!used[t]) dfs(t, k, v, rv); } vs.push_back(n); } // 強連結成分分解を行う. int scc(){ int N = size(); used.assign(N, false); order.resize(N); vs.clear(); // 辺を逆にしたグラフ用. vector rG(N), tmp(N); for(int n = 0; n < N; n++) if(!used[n]) dfs(n, n, (*this), rG); used.assign(N, false); // 強連結成分の番号. int k = 0; for(int i = vs.size() - 1; i >= 0; i--) if(!used[vs[i]]) dfs(vs[i], k++, rG, tmp); return k; } // 属する強連結成分が同じかどうか判定. bool find(int x, int y){ return order[x] == order[y]; } }; // 関数としてsccを使う。戻り値は、各ノードが所属する強連結成分の番号 vector scc(const vector &v){ SCCGraph g(v); g.scc(); return g.order; } // 2-SAT struct TwoSAT{ SCCGraph graph; int N; // 結果. vector val; TwoSAT(int n): graph((n + 1) * 2), val(n + 1) { N = n; } // 辺(a -> b)を追加, 負の値は, 論理変数の否定(~a). void add_edge(int a, int b){ if(a < 0) a = N - a; if(b < 0) b = N - b; graph.add_edge(a, b); } // 論理式(a V b)を追加, a, bは, 論理変数の番号(0以外の整数), 否定は負の値. void add_or(int a, int b){ add_edge(-a, b); add_edge(-b, a); } // 判定. bool solve(){ graph.scc(); bool ret = true; for(int i = 1; i <= N; i++){ if(graph.order[i] == graph.order[N+i]) ret = false; val[i] = (graph.order[i] > graph.order[N+i]); } return ret; } // 変数の値を取得. bool value(int a){ if(a < 0) return !val[-a]; return val[a]; } }; int main(){ int N, M; int L[2005], R[2005], rL[2005], rR[2005]; TwoSAT sat(2005); cin >> N >> M; for(int i = 0; i < N; i++){ cin >> L[i] >> R[i]; // 180度回転 rR[i] = M - L[i] - 1; rL[i] = M - R[i] - 1; } auto fn = [&](int Li, int Lj, int Ri, int Rj, int a, int b){ // 重なる可能性があるものはadd if(!(Rj < Li || Ri < Lj)) sat.add_or(-a, -b); }; for(int i = 0; i < N; i++) for(int j = 0; j < i; j++){ fn( L[i], L[j], R[i], R[j], (i + 1), (j + 1)); fn(rL[i], L[j], rR[i], R[j], -(i + 1), (j + 1)); fn( L[i], rL[j], R[i], rR[j], (i + 1), -(j + 1)); fn(rL[i], rL[j], rR[i], rR[j], -(i + 1), -(j + 1)); } cout << (sat.solve() ? "YES" : "NO") << endl; return 0; }