#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; template T read(std::istream& is) { T value; is >> value; return value; } template std::istream& operator>>(std::istream& is , std::tuple& tuple) { tuple = std::make_tuple( read(is)... ); return is; } const int MAX_V = 6000; vector G[MAX_V]; vector rG[MAX_V]; vector vs; bool used[MAX_V]; int cmp[MAX_V]; void add_edge(int from, int to) { G[from].push_back(to); rG[to].push_back(from); } void dfs(int v) { used[v] = true; for(int i=0; i=0; i--) { if(!used[vs[i]]) rdfs(vs[i], k++); } return k; } const int MAX_N = 2001; int N, M; using tpl = tuple; tpl lr[MAX_N * 2]; bool uncover(tpl a, tpl b) { auto&& al = get<0>(a), &&ar = get<1>(a); auto&& bl = get<0>(b), &&br = get<1>(b); return !( (bl <= al && al <= br) || (bl <= ar && ar <= br) || (al <= bl && bl <= ar) || (al <= br && br <= ar) ); } int main() { cin >> N >> M; rep(i, N) { cin >> lr[i]; lr[N+i] = make_tuple(M-1-get<1>(lr[i]), M-1-get<0>(lr[i])); //printf("(%d, %d) -> (%d, %d)\n", get<0>(lr[i]), get<1>(lr[i]), get<0>(lr[N+i]), get<1>(lr[N+i])); } /* 基本形: p -> q <=> ~q -> ~p <=> ~p v q <=> ~(p ∧ ~q) p, q の符号の組み合わせをすべて試す */ rep(i, N) REP(j, i+1, N) { // p -> ~q <=> q -> ~p <=> ~p v ~q <=> ~(p ∧ q) if(!uncover(lr[i], lr[j])) { add_edge(j, N+i); add_edge(i, N+j); } // ~p -> ~q <=> q -> p <=> p v ~q <=> ~(~p ∧ q) if(!uncover(lr[N+i], lr[j])) { add_edge(N+i, N+j); add_edge(j, i); } // p -> q <=> ~q -> ~p <=> ~p v q <=> ~(p ∧ ~q) if(!uncover(lr[i], lr[N+j])) { add_edge(i, j); add_edge(N+j, N+i); } // ~p -> q <=> ~q -> p <=> p v q <=> ~(~p ∧ ~q) if(!uncover(lr[N+i], lr[N+j])) { add_edge(N+i, j); add_edge(N+j, i); } } scc(); rep(i, N) { if(cmp[i] == cmp[N+i]) { cout << "NO" << endl; return 0; } } cout << "YES" << endl; return 0; }