#include using namespace std; using ll = long long; using ld = long double; using pint = pair; using pll = pair; using pld = pair; const int INF=1e9+7; const ll LINF=9223372036854775807; const ll MOD=1e9+7; const ld PI=acos(-1); const ld EPS = 1e-10; //微調整用(EPSより小さいと0と判定など) int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; } long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; } string is() { string x; cin >> x; return x; } char ic() { char x; cin >> x; return x; } void oi(int x) { printf("%d ", x); } void ol(long long x) { printf("%lld ", x); } void od_nosp(double x) { printf("%.15f", x); } // 古い問題用 void od(double x) { printf("%.15f ", x); } // long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る // それをなんとかするには独自の出力を作らなければならなそう void os(const string &s) { printf("%s ", s.c_str()); } void oc(const char &c) { printf("%c ", c); } #define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認 void br() { putchar('\n'); } // #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意 // int lcm(int a, int b){return a / gcd(a, b) * b;} #define begin_end(a) a.begin(),a.end() //sort(begin_end(vec)); #define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll) (n) ; i++ ) #define rep(i,n) REP(i,0,n) #define m_p(a,b) make_pair(a,b) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin()) #define p_b push_back #define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに // coutによるpairの出力(空白区切り) template ostream& operator<<(ostream& s, const pair& p) {return s << "(" << p.first << " " << p.second << ")";} // coutによるvectorの出力(空白区切り) template ostream& operator<<(ostream& s, const vector& v) { int len = v.size(); for (int i = 0; i < len; ++i) { s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る } return s; } // coutによる多次元vectorの出力(空白区切り) template ostream& operator<<(ostream& s, const vector< vector >& vv) { int len = vv.size(); for (int i = 0; i < len; ++i) { s << vv[i] << endl; } return s; } //最大値、最小値の更新。更新したor等しければtrueを返す template bool chmax(T& a, T b){return (a = max(a, b)) == b;} template bool chmin(T& a, T b){return (a = min(a, b)) == b;} //4近傍(上下左右) rep(i, 2) にすると右・下だけに進む vector dx_4 = {1, 0, -1, 0}; vector dy_4 = {0, 1, 0, -1}; // -------- template end - // // - library ------------- // // 2-SAT // (出典)https://kopricky.github.io/code/Computation_Advanced/two_sat.html // (a∨b) ∧ (¬b∨c) ∧ … といった、各クロージャ内のリテラル数が高々2個であるようなな命題論理式(2-SAT)の充足可能性を判定 // satisfy() が true(充足可能) であれば、vector ans に、与えられた2-SATを充足するような 各リテラル[i] の 真偽(1or0)を格納する // 各リテラル Xi と その否定 ¬Xi を頂点と考えて、強連結成分分解によって解く。 // O(リテラル数 + クロージャ数) // なお、¬a∨¬b は 「aとbは両立しない」と言い換えられる。 // 参考 : https://yukicoder.me/problems/no/274 // 使い方 // ll n = リテラル数; // TwoSAT two_sat(n); // - ※a,¬a,b,¬b,c,¬c があるとき、n = 3 。頂点倍加はライブラリ内で行う。 // for(各クロージャ) add_closure(x, y); // これは クロージャ (x∨y) の例 // - 否定(¬xや¬y)を入れたい時は +n する。ex) (¬x∨y) -> (x+n, y); // if (two_sat.satisfy()) rep(i, n) cout << two_sat.ans[i] << endl; // else cout << "impossible" << endl; class TwoSAT { private: const ll V; vector > G, rG; vector ps, cmp; void add_edge(ll from, ll to){ G[from].push_back(to), rG[to].push_back(from); } void dfs(ll u){ cmp[u] = 0; for(ll v : G[u]){ if(cmp[v] == -1) dfs(v); } ps.push_back(u); } void rdfs(ll u, ll k){ cmp[u] = k; for(ll v : rG[u]){ if(cmp[v] == -1) rdfs(v, k); } } ll scc(){ for(ll i = 0; i < 2 * V; ++i){ if(cmp[i] == -1) dfs(i); } fill(cmp.begin(), cmp.end(), -1); ll k = 0; for(ll i = 2 * V - 1; i >= 0; --i){ if(cmp[ps[i]] == -1) rdfs(ps[i], k++); } return k; } public: vector ans; TwoSAT(const ll literal_count) : V(literal_count), G(2 * V), rG(2 * V), cmp(2 * V, -1), ans(V){} void add_closure(ll x, ll y){ add_edge((x + V) % (2 * V), y), add_edge((y + V) % (2 * V), x); } // 充足可能性判定 // 真のものは 1,偽のものは 0 が ans に格納される(解の構成) bool satisfy(){ scc(); for(ll i = 0; i < V; i++){ if(cmp[i] == cmp[V + i]) return false; ans[i] = (cmp[i] > cmp[V + i]); } return true; } }; // --------- library end - // int main(){ ll N, M; cin >> N >> M; // 使い方 // ll n = リテラル数; // TwoSAT two_sat(n); // - ※a,¬a,b,¬b,c,¬c があるとき、n = 3 。頂点倍加はライブラリ内で行う。 // for(各クロージャ) add_closure(x, y); // これは クロージャ (x∨y) の例 // - 否定(¬xや¬y)を入れたい時は +n する。ex) (¬x∨y) -> (x+n, y); // if (two_sat.satisfy()) rep(i, n) cout << two_sat.ans[i] << endl; // else cout << "impossible" << endl; vector LRs(N * 2, pll()); rep(i, N){ ll l = il(); ll r = il(); LRs[i] = m_p(l, r); LRs[i+N] = m_p(M-1-r, M-1-l); } TwoSAT two_sat(N); // リテラル = ブロック rep(i, N) rep(j, i){ // i: 0~N-1, j: 0~i-1 なので、実質 i: 1~N-1, j: 0~i-1 // つまり、j < i な 各ブロックについてループ // i と j のピンク区間がかぶったとき、iとj, ¬iと¬jが両立しないので、(¬i∨¬j) ∧ (i∨j) // 区間がかぶる = !(iR < jL || jR < iL) if (!(LRs[i].second < LRs[j].first || LRs[j].second < LRs[i].first)){ two_sat.add_closure(i+N, j+N); two_sat.add_closure(i, j); } // i と ¬j のピンク区間がかぶったとき、iと¬j, ¬iとjが両立しないので、(¬i∨j) ∧ (i∨¬j) if (!(LRs[i].second < LRs[j+N].first || LRs[j+N].second < LRs[i].first)){ two_sat.add_closure(i+N, j); two_sat.add_closure(i, j+N); } } if (two_sat.satisfy()) cout << "YES" << endl; else cout << "NO" << endl; }