#include #include #include #include #include #include #include #include #include #include #include #include #include using ll = long long; const ll INF = 1 << 29; class TwoSAT { public: TwoSAT(const int literal_count) : V(literal_count), connection(2 * V), reversedConnection(2 * V), cmp(2 * V, -1){} void AddClosure(int x, int y) { AddEdge(x, y); // !x, !y が inout 似ない場合はこっち // AddEdge((x + V) % (2 * V), y); // !x -> y // AddEdge((y + V) % (2 * V), x); // !y -> x } std::pair> Satisfy() { SCC(); std::vector ans(V); for(auto i = 0; i < V; i++) { // x -> !x 成り立つ = 同じグラフ上にあるとき充足不可能(矛盾) if(cmp[i] == cmp[V + i]) return std::make_pair(false, ans); // そうでなければ充足可能な変数の組み合わせが存在する. // x が !x のトポロジカル順序より後なら x は真 // ( dfs の探索順で先に判明した組み合わせの値を解として返す ) ans[i] = (cmp[V + i] < cmp[i]); } return std::make_pair(true, ans); } private: const int V; std::vector> connection, reversedConnection; std::vector ps, cmp; void AddEdge(int from, int to) { connection[from].push_back(to); reversedConnection[to].push_back(from); } void DFS(int u) { cmp[u] = 0; for(auto v : connection[u]) { if(cmp[v] == -1) DFS(v); } ps.push_back(u); } void RDFS(int u, int k) { cmp[u] = k; for(auto v : reversedConnection[u]) { if(cmp[v] == -1) RDFS(v, k); } } void SCC() { for(auto i = 0; i < 2 * V; ++i) { if(cmp[i] == -1) DFS(i); } fill(cmp.begin(), cmp.end(), -1); int k = 0; for(auto i = 2 * V - 1; 0 <= i; --i) { if(cmp[ps[i]] == -1) RDFS(ps[i], k++); } } }; int main() { int N, M; std::cin >> N >> M; TwoSAT sat(N); std::vector L(N); std::vector R(N); std::vector revL(N); std::vector revR(N); for (auto i=0; i> L[i] >> R[i]; revR[i] = M - L[i] - 1; revL[i] = M - R[i] - 1; } for (auto i=0; i どっちか回転 (B && !A) or (!B && A) if(L[i] <= R[j] && L[j] <= R[i]) { sat.AddClosure(i, j + N); sat.AddClosure(i + N, j); } // 反転したB が A に含まれてる -> Bを回転しない or Aを回転 (!B && !A) or (B && A) if(L[i] <= revR[j] && revL[j] <= R[i]) { sat.AddClosure(i, j); sat.AddClosure(i + N, j + i); } // B が 反転したA に含まれてる -> Bを回転 or Aを回転しない : (!A && !B) or (A && B) if(revL[i] <= R[j] && L[j] <= revR[i]) { sat.AddClosure(j + N, i + N); sat.AddClosure(j, i); } // 反転したB が 反転したA に含まれてる -> どっちか回転 : (!A && B) or (A && !B) if(revL[i] <= revR[j] && revL[j] <= revR[i]) { sat.AddClosure(j + N, i); sat.AddClosure(j, i + N); } } } auto result = sat.Satisfy(); if (!result.first) std::cout << "NO" << std::endl; else std::cout << "YES" << std::endl; }