#include using namespace std; #if __has_include() #include #endif using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i(0) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i struct Edge{ int from,to; T weight; int index; Edge(int from_,int to_,T weight_=T(),int index_=-1):from(from_),to(to_),weight(weight_),index(index_){} Edge():from(-1),to(-1),weight(),index(-1){} friend std::ostream &operator<<(std::ostream &os,const Edge&e){ os<<'['; os<<"from:"< struct Graph{ private: int n; vector>edge; vector>g; vectorptr; bool directed; struct graph_range{ using iterator=typename vector>::iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} Edge &operator[](int i)const{return l[i];} }; struct const_graph_range{ using iterator=typename vector>::const_iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} const Edge &operator[](int i)const{return l[i];} }; public: Graph(int n_,bool dir_):n(n_),directed(dir_){} Graph():n(0){} Graph(int n_,bool dir_,const vector>&e):n(n_),directed(dir_),edge(e){build();} template void read(int m){ edge.reserve(m); for(int i=0;i>u>>v; T w; if constexpr(index)u--,v--; if constexpr(weighted)cin>>w; else w=1; edge.emplace_back(u,v,w,i); } build(); } void add_edge(int u,int v){ int id=edge.size(); edge.emplace_back(u,v,1,id); } void add_edge(int u,int v,T w){ int id=edge.size(); edge.emplace_back(u,v,w,id); } void add_edge(int u,int v,T w,int index){ edge.emplace_back(u,v,w,index); } void build(){ vectorcnt(n+1,0); for(const Edge&e:edge){ cnt[e.from+1]++; if(!directed)cnt[e.to+1]++; } for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1]; ptr=cnt; g.resize(cnt[n]); for(const Edge&e:edge){ g[cnt[e.from]++]=e; if(!directed)g[cnt[e.to]++]=Edge(e.to,e.from,e.weight,e.index); } } void reverse(){ if(directed){ for(Edge&e:edge)swap(e.from,e.to); build(); } } inline void to_directed(){ directed=true; build(); } inline void to_undirected(){ directed=false; build(); } void reserve(int m){edge.reserve(m);} graph_range operator[](int i){return graph_range{g.begin()+ptr[i],g.begin()+ptr[i+1]};} const_graph_range operator[](int i)const{return const_graph_range{g.begin()+ptr[i],g.begin()+ptr[i+1]};} const Edge& get_edge(int i)const{return edge[i];} inline bool is_directed()const{return directed;} inline int size()const{return n;} inline int edge_size()const{return edge.size();} }; template vectorstrongly_connected_components(Graphg){ int n=g.size(); vectorseen(n,false); vectorst(g.edge_size()+1); int p=0; vectorvis; vis.reserve(n); for(int i=0;i0){ int x=st[--p]; if(x<0){ vis.push_back(~x); continue; } if(seen[x])continue; seen[x]=true; st[p++]=~x; for(const Edge&e:g[x])if(!seen[e.to])st[p++]=e.to; } } vectorscc(n,-1); g.reverse(); int sp=0; for(int i=n-1;i>=0;i--)if(scc[vis[i]]==-1){ st[p++]=vis[i]; while(p>0){ int x=st[--p]; scc[x]=sp; for(const Edge&e:g[x])if(scc[e.to]==-1)st[p++]=e.to; } sp++; } return scc; } using namespace std; vectortwo_sat(int n,const vector>&a){ Graphg(n*2,true); g.reserve(a.size()*2); for(const auto&[u,v]:a){ if(u>=0&&v>=0){ g.add_edge(u+n,v); g.add_edge(v+n,u); } else if(u>=0){ g.add_edge(u+n,(~v)+n); g.add_edge(~v,u); } else if(v>=0){ g.add_edge(~u,v); g.add_edge(v+n,(~u)+n); } else{ g.add_edge(~u,(~v)+n); g.add_edge(~v,(~u)+n); } } g.build(); vectorscc=strongly_connected_components(g); vectorret(n); for(int i=0;i{}; ret[i]=scc[i]>scc[i+n]; } return ret; } void SOLVE(){ int n,m; cin>>n>>m; vector>a(n); rep(i,n){ cin>>a[i]; a[i].second++; } vector>b; rep(i,n-1)reps(j,i+1,n){ bool f=max(a[i].first,a[j].first)>=min(a[i].second,a[j].second); bool g=max(a[i].first,m-a[j].second)>=min(a[i].second,m-a[j].first); if(f&&g)continue; else if(!f&&!g)fin("NO"); else if(f){ b.push_back({~i,j}); b.push_back({i,~j}); } else{ b.push_back({i,j}); b.push_back({~i,~j}); } } cout<<(two_sat(n,b).size()?"YES":"NO")<