#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class SCC { public: // for input or output data std::vector> G_; std::vector cmp_; // for algorithm std::vector> rG_; std::vector vs_; std::vector used_; SCC() {} SCC(int V) { init(V); } void init(int V) { G_.resize(V); rG_.resize(V); used_.resize(V); cmp_.resize(V); } ~SCC() {} void add(int from, int to) { assert(0 <= from && from < (int)G_.size()); assert(0 <= to && to < (int)rG_.size()); G_[from].push_back(to); rG_[to].push_back(from); } void dfs(int v) { used_[v] = true; for (int i = 0; i < (int)G_[v].size(); ++i) { if (!used_[G_[v][i]]) dfs(G_[v][i]); } vs_.push_back(v); } void rdfs(int v, int k) { used_[v] = true; cmp_[v] = k; for (int i = 0; i < (int)rG_[v].size(); ++i) { if (!used_[rG_[v][i]]) rdfs(rG_[v][i], k); } } // // O(|V|+|E|) // int decompose() { int V = G_.size(); std::fill(used_.begin(), used_.end(), false); vs_.clear(); for (int v = 0; v < V; ++v) if (!used_[v]) dfs(v); std::fill(used_.begin(), used_.end(), false); int k = 0; for (int i = vs_.size()-1; i >= 0; i--) if (!used_[vs_[i]]) rdfs(vs_[i], k++); return k; } const std::vector &components() const { return cmp_; } }; class TwoSAT : public SCC { public: int n_; vector logic_; int True(int x) { return x; } int Fals(int x) { return (x+n_)%(2*n_); } TwoSAT(int nVar) { init(nVar); } void init(int nVar) { logic_.resize(nVar, false); n_ = nVar; SCC::init(nVar*2); } void add(int x1, int x2) { SCC::add(True(x1), True(x2)); SCC::add(Fals(x2), Fals(x1)); // add contraposition edge } void setTrue(int x) { SCC::add(Fals(x), True(x)); } void setFalse(int x) { SCC::add(True(x), Fals(x)); } bool solve() { SCC::decompose(); for (int i = 0; i < n_; i++) { int a = SCC::cmp_[True(i)]; int b = SCC::cmp_[Fals(i)]; if (a == b) return false; logic_[i] = (a > b); } return true; } }; bool rangeIsCross(int s1, int e1, int s2, int e2) { return max(s1,s2) <= min(e1,e2); } class TheWall { public: bool rangeIsCross(const pair &a, const pair &b) { return ::rangeIsCross(a.first, a.second, b.first, b.second); } void solve(void) { int N,M; cin>>N>>M; vector> blks; REP(i,N) { int l,r; cin>>l>>r; blks.emplace_back(l,r); } TwoSAT sat(N); #define T(x) sat.True(x) #define F(x) sat.Fals(x) // block 反転(first,second が逆になる) #define flip(BLK) make_pair(M-1-(BLK).second, M-1-(BLK).first) REP(i,N) { REP(j,i) { // 交差しないときに辺を張るのではなくて、 // 交差するときにそれを回避するための制約として辺を張る if (rangeIsCross(blks[i], blks[j])) sat.add(T(i),F(j)); if (rangeIsCross(blks[i],flip(blks[j]))) sat.add(T(i),T(j)); if (rangeIsCross(flip(blks[i]),blks[j])) sat.add(F(i),F(j)); if (rangeIsCross(flip(blks[i]),flip(blks[j]))) sat.add(F(i),T(j)); } } if ( sat.solve() ) cout<<"YES"<solve(); delete obj; return 0; } #endif