#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_; } }; 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); } SCC scc(N*2); #define flip(BLK) make_pair(M-1-(BLK).second, M-1-(BLK).first) REP(i,N) { // 対偶も追加 #define Add(X,Y) do { scc.add(X,Y); scc.add((Y+N)%(2*N), (X+N)%(2*N));} while(0) REP(j,i) { // 交差しないときに辺を張るのではなくて、 // 交差するときにそれを回避するための制約として辺を張る if (rangeIsCross(blks[i], blks[j])) Add(i,j+N); if (rangeIsCross(blks[i],flip(blks[j]))) Add(i,j); if (rangeIsCross(flip(blks[i]),blks[j])) Add(i+N,j+N); if (rangeIsCross(flip(blks[i]),flip(blks[j]))) Add(i+N,j); } } scc.decompose(); REP(i,N) { if ( scc.cmp_[i] == scc.cmp_[i+N] ) { cout<<"NO"<solve(); delete obj; return 0; } #endif