#include #include #include using namespace std; void dfs1(vector>> &graph, vector &num, vector &used, int node, int &con){ if(used[node]) return ; used[node] = true; for(pair next : graph[node]){ dfs1(graph, num, used, next.first, con); } num[con++] = node; } void dfs2(vector>> &graph, vector &scc, vector &used, int node, int same){ if(used[node]) return ; used[node] = true; for(pair next : graph[node]){ dfs2(graph, scc, used, next.first, same); } scc[node] = same; } void Strongly_Connected_Components(vector>> &graph, vector &scc){ vector used(graph.size()), num(graph.size()); vector>> graph2(graph.size()); int con = 0; scc.resize(graph.size()); for(int i = 0; i < graph.size(); i++){ dfs1(graph, num, used, i, con); } for(int i = 0; i < graph.size(); i++){ for(int j = 0; j < graph[i].size(); j++){ graph2[graph[i][j].first].push_back(make_pair(i, graph[i][j].second)); } } used.clear(); used.resize(graph.size()); for(int i = (int)graph.size()-1, same = 0; i >= 0; i--){ if(!used[num[i]]){ dfs2(graph2, scc, used, num[i], same); same++; } } } bool two_satisfiability(int num, vector,pair>>& closure, vector& val){ vector>> graph(num*2); vector scc; val.resize(num); for(int i = 0; i < closure.size(); i++){ graph[!closure[i].first.first + closure[i].first.second*2].push_back({closure[i].second.first + closure[i].second.second*2 ,0}); graph[!closure[i].second.first + closure[i].second.second*2].push_back({closure[i].first.first + closure[i].first.second*2 ,0}); } Strongly_Connected_Components(graph, scc); for(int i = 0; i < num*2; i += 2){ if(scc[i] == scc[i+1]){ return false; } else if(scc[i] > scc[i+1]){ val[i/2] = true; } else { val[i/2] = false; } } return true; } bool check(pair a, pair b){ bool res; res = (a.second - a.first + 1 + b.second - b.first + 1 > max(a.second, b.second) - min(a.first, b.first) + 1); return res; } signed main(){ int N, M; vector> in; vector val; vector,pair>> closure; cin>>N>>M; in.resize(N); for(int i = 0; i < N; i++){ int L, R; cin>>in[i].first>>in[i].second; } for(int i = 0; i < N; i++){ for(int j = i+1; j < N; j++){ pair ri{M-in[i].second-1, M-in[i].first-1}, rj{M-in[j].second-1, M-in[j].first-1}; if(check(in[i], in[j])) { closure.push_back({{true,i},{true,j}}); } if(check(in[i], rj)) { closure.push_back({{true,i},{false,j}}); } if(check(ri, in[j])) { closure.push_back({{false,i},{true,j}}); } if(check(ri, rj)) { closure.push_back({{false,i},{false,j}}); } } } if(two_satisfiability(N, closure, val)){ cout<<"YES"<