#line 1 "base.hpp"//3 #ifndef __clang__ #pragma GCC optimize ("O3") #endif void solve( #ifdef GCJ_CASE long long case_id #endif ); #if defined(EBUG) && !defined(ONLINE_JUDGE) #define debug true #define _GLIBCXX_DEBUG // #define _LIBCPP_DEBUG 0 #define _LIBCPP_DEBUG2 0 #else #define NDEBUG #define debug false #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using LL=long long; using ULL=unsigned long long; #define int LL #define CS const #define CX constexpr #define IL inline #define OP operator #define RT return #define TL template #define TN typename #define lambda [&] #define rep(f,t,i,c,u)for(int Rb_=(t),i=(f);i c Rb_;u(i)) #define upto(f,t,i)rep(f,t,i,<=,++) #define uptil(f,t,i)rep(f,t,i,<,++) #define downto(f,t,i)rep(f,t,i,>=,--) #define downtil(f,t,i)rep(f,t,i,>,--) #define times(n,i)uptil(0,n,i) #define rtimes(n,i)downto((n)-1,0,i) #define iter(v)begin(v),end(v) #define citer(v)cbegin(v),cend(v) #define riter(v)rbegin(v),rend(v) #define criter(v)crbegin(v),crend(v) #define IF(a,b,c)((a)?(b):(c)) #if debug #define ln <,f1,f2,x)CMPOP(t,>=,f1,f2,x) #line 1 "mod.hpp"//3b #ifndef MOD #define MOD 1000000007 #endif #if !defined(FORCE_MOD)&&MOD!=1000000007&&MOD!=1000000009&&MOD!=998244353 #error mod #endif #line 1 "power.hpp"//3bm TLIL T power(T x,int n){T r(1);for(;n;n/=2){if(n%2)r*=x;x*=x;}RT r;}IL int pow_mod(int x,int n,int m){int r=1; for(;n;n/=2){if(n%2)r=r*x%m;x=x*x%m;}RT r;} #line 2001 "mod.hpp"//3b IL CX int modulo(int a,int b){a%=b;RT a&&(a>0)!=(b>0)?a+b:a;}IL CX int divide(int a,int b){RT(a-modulo(a,b))/b;} TLstruct MInt{ /*!https://ei1333.github.io/luzhiled/snippets/other/mod-int.html*/ int v;CX MInt():v(0){}explicit CX MInt(int i):v(modulo(i,d)){}MInt&OP+=(CS MInt&m){v+=m.v;if(v>=d)v-=d;RT*this;} MInt&OP-=(CS MInt&m){v-=m.v;if(v<0)v+=d;RT*this;}MInt&OP*=(CS MInt&m){v=v*m.v%d;RT*this;}MInt&OP/=(CS MInt&m){ RT*this*=m.inv();}BINOPa(MInt,MInt,+)BINOPa(MInt,MInt,-)BINOPa(MInt,MInt,*)BINOPa(MInt,MInt,/)MInt OP-()CS{ RT MInt()-=*this;}CMPOP(MInt,==,v,m.v,m)CMPOP(MInt,!=,v,m.v,m)MInt pow(int n)CS{RT power(*this,n);}MInt inv()CS{ int a=v,b=d,x=1,y=0;while(b){swap(y,x-=a/b*y);swap(b,a%=b);}RT(MInt)x;} friend ostream&OP<<(ostream&o,CS MInt&m){RT o<>(istream&i,MInt&m){i>>m.v;m.v%=d;RT i;}}; using mint=MInt<>;CX mint OP"" _m(ULL n){RT mint(n);}CX MInt<998244353>OP"" _m998244353(ULL n){RT MInt<998244353>(n);} CX MInt<1000000007>OP"" _m1e9_7(ULL n){RT MInt<1000000007>(n);} CX MInt<1000000009>OP"" _m1e9_9(ULL n){RT MInt<1000000009>(n);} #line 1 "typedefs.hpp"//3b using unit = tuple<>;using int128=__int128;using LD=long double;TLusing vec=vector; TLusing vvec=vec>;TLusing vvvec=vec>;TLusing vvvvec=vec>; using VB=vec;using VI=vec;using WI=vvec;using PBI=pair;using PBVB=pair>;using WPBI=vvec>; #line 1 "alias.hpp"//3b #define EB emplace_back #define PB push_back #define foldl accumulate #define scanl partial_sum #line 1 "util.hpp"//3b TLIL bool amax(T&v,CS T&a){RT vIL bool amin(T&v,CS T&a){RT v>a&&(v=a,1);} TLIL int sizeRAB(T t){RT t.size();} #define size sizeRAB #define clamp clampRAB TLIL CX CS T&clamp(CS T&a,CS T&l,CS T&r){RT aIL void uniq2(V&v){ v.erase(unique(iter(v)),v.end());}TLIL void uniq(V&v){sort(iter(v));uniq2(v);} #define leftmost_ge lower_bound #define leftmost_gt upper_bound namespace rab{TLIL bool is_in(I x,I l,I r){RT l<=x&&xIL T fetch(CS T&d,CS vec&v,int i){ RT 0<=i&&iIL istream&OP>>(istream&s,vec&v){for(auto&&p:v)s>>p;RT s;}TL IL ostream&OP<<(ostream&s,CS pair&p){RT s<<"("<Rdebug1(' ',vec)TLRdebug1(' ',map)TLRdebug1('\n',vvec) TLRdebug1('\n',vec>) #line 6001 "base.hpp"//3 signed main(){if(debug)cerr<<"MOD: "<>T;times(T,t){cout<<"Case #"<struct Edge{int from;int to;E weight;Edge(int from,int to,E weight):from(from),to(to),weight(weight){} CMPOPS(Edge,make_tuple(weight,from,to),make_tuple(e.weight,e.from,e.to),e)};TLclass Graph{protected:int nv_,nde_; public:vvec>edges;Graph(int nv):nv_(nv),nde_(0),edges(nv){}IL int nv()CS{RT nv_;}IL int nde()CS{RT nde_;} IL int nue()CS{RT nde_/2;}IL void add_dedge(int i,int j,CS E&val){if(debug&&(i<0||nv_<=i||j<0||nv_<=j)){ cerr<<"invalid index:("<struct SCCer{int n;Graphscc;CS Graph&g;Graphgrev;VB visited;VI po,zip;WI unzip; SCCer(CS Graph&g):n(g.nv()),scc(0),g(g),grev(n),visited(n),zip(n,-1){po.reserve(n); times(n,i)for(CS auto&e:g.edges[i]){grev.add_dedge(e.to,e.from,{});}}private:void po_dfs(int i){if(visited[i])RT; visited[i]=1;for(CS auto&e:g.edges[i])po_dfs(e.to);po.PB(i);}void zip_rdfs(int i,int z){if(~zip[i])RT;zip[i]=z; for(CS auto&e:grev.edges[i])zip_rdfs(e.to,z);}public:void exec(){times(n,i)po_dfs(i);int z=0; for(auto it=po.rbegin();it!=po.rend();++it)if(zip[*it]==-1)zip_rdfs(*it,z++);scc=decltype(scc)(z);unzip.resize(z); for(auto it=po.rbegin();it!=po.rend();++it){int x=zip[*it];unzip[x].PB(*it);for(CS auto&e:g.edges[*it]){ int y=zip[e.to];if(x!=y)assert(xg(n*2);for(auto&ts:sat){int z=size(ts);if(z==1)g.add_dedge(sat2x(n,ts[0],1),sat2x(n,ts[0]),{});else if(z==2) g.add_dedge(sat2x(n,ts[0],1),sat2x(n,ts[1]),{}),g.add_dedge(sat2x(n,ts[1],1),sat2x(n,ts[0]),{}); else cerr<<"invalid sat",exit(1);}SCCersccer(g);sccer.exec();VB ans(n);times(n,i){int x=sccer.zip[i],y=sccer.zip[i+n]; if(x==y)RT{0,{}};ans[i]=x>y;}RT{1,ans};} #line 3001 "3.cpp"// void solve() { // NMN(LR) int N;int M;cin>>N;cin>>M;VI L(N);VI R(N);times(N,Ri_0){cin>>L[Ri_0];cin>>R[Ri_0 ];} WPBI sat; sat.reserve(N * (N - 1) / 2); times(N, i) times(i, j) { bool b1 = L[i] <= R[j] && L[j] <= R[i], b2 = L[i] <= M-1-L[j] && M-1-R[j] <= R[i]; if(b1 && b2) { cout << dict::NO ln; exit(0); } if(b1) { sat.PB({{false, i}, {false, j}}); sat.PB({{true, i}, {true, j}}); } if(b2) { sat.PB({{false, i}, {true, j}}); sat.PB({{true, i}, {false, j}}); } } auto r = sat2(N, sat); cout << IF(r.first, dict::YES, dict::NO) ln; }