//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef DEBUG #include "./CompetitiveProgrammingCpp/debug_VC.hpp" #include "./CompetitiveProgrammingCpp/Timer.hpp" #include "./CompetitiveProgrammingCpp/sample.hpp" #else #define dump(...) #endif /* macro */ #define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i) #define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) RFOR(i, 0, n) #define REPC(x,c) for(const auto& x:(c)) #define REPI2(it,b,e) for(auto it = (b); it != (e); ++it) #define REPI(it,c) REPI2(it, (c).begin(), (c).end()) #define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend()) #define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);) #define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end()) #define ALL(x) (x).begin(),(x).end() #define cauto const auto& /* macro func */ template inline auto sort(T& t) { std::sort(ALL(t)); } template inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); } template inline auto unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); } template inline auto chmax(T& t, const S& s) { if (s > t) { t = s; return true; } return false; } template inline auto chmin(T& t, const S& s) { if (s < t) { t = s; return true; } return false; } inline auto BR() { std::cout << "\n"; } /* type define */ using ll = long long; using PAIR = std::pair; using VS = std::vector; using VL = std::vector; using VVL = std::vector; using VVVL = std::vector; using VD = std::vector; template using V = std::vector; /* using std */ using std::cout; constexpr char endl = '\n'; using std::cin; using std::pair; using std::string; using std::stack; using std::queue; using std::vector; using std::list; using std::map; using std::unordered_map; using std::multimap; using std::unordered_multimap; using std::set; using std::unordered_set; using std::unordered_multiset; using std::multiset; using std::bitset; using std::priority_queue; /* Initial processing */ struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing; /* Remove the source of the bug */ auto pow(signed, signed) { assert(false); return -1; } /* define hash */ namespace std { template <> class hash> { public: size_t operator()(const std::pair& x) const { return hash()(1000000000 * x.first + x.second); } }; } /* input */ template std::istream& operator >> (std::istream& is, vector& vec) { for (T& x : vec) is >> x; return is; } /* constant value */ //constexpr ll MOD = 1000000007; constexpr ll MOD = 998244353; //============================================================================================= class SCC { const int m_n; const std::unordered_multimap m_graph; const std::unordered_multimap m_revGraph; const std::vector m_group; auto reverse()const { std::unordered_multimap graph; for (const auto& [f, t] : m_graph) { graph.emplace(t, f); } return graph; } template auto dfs(int n, const std::unordered_multimap& graph, int root, std::vector& isUsed, const Lambda& lambda) const { isUsed[root] = true; std::stack q; q.emplace(root); while (!q.empty()) { auto from = q.top(); q.pop(); auto range = graph.equal_range(from); for (auto itr = range.first; itr != range.second; ++itr) { auto to = itr->second; if (!isUsed[to]) { q.emplace(to); isUsed[to] = true; lambda(from, to); } } } } auto constructGroup()const { std::list order; { std::vector used(m_n); for (int from = 0; from < m_n; ++from) if (!used[from]) { std::list localOrder; localOrder.emplace_front(from); dfs(m_n, m_graph, from, used, [&](int f, int t) { used[t] = true; localOrder.emplace_front(t); }); for (const auto& x : localOrder) { order.emplace_front(x); } } } std::vector group(m_n); { std::vector used(m_n); int g = 0; for (const auto& from : order) if (!used[from]) { group[from] = g; dfs(m_n, m_revGraph, from, used, [&](int f, int t) { used[t] = true; group[t] = g; }); ++g; } } return group; } public: SCC(int n, const std::unordered_multimap& graph) : m_n(n), m_graph(graph), m_revGraph(reverse()), m_group(constructGroup()) { } auto isSameGroup(int a, int b)const { return m_group[a] == m_group[b]; } }; signed main() { ll n, m; cin >> n >> m; V v; ll sum = 0; v.reserve(2 * n); REP(_, n) { ll a, b; cin >> a >> b; v.emplace_back(a, b); sum += b - a + 1; } if (sum > m) { cout << "NO" << endl; return 0; } REP(i, n) { v.emplace_back(m - v[i].second - 1, m - v[i].first - 1); } unordered_multimap graph; REP(i, 2 * n)FOR(j, i + 1, 2 * n) { if (v[i].second < v[j].first || v[j].second < v[i].first) { continue; } ll ni = (i < n) ? i + n : i - n; ll nj = (j < n) ? j + n : j - n; graph.emplace(ni, j); graph.emplace(nj, i); } auto scc = SCC(2 * n, graph); REP(i, n) if (scc.isSameGroup(i, i + n)) { cout << "NO" << endl; return 0; } cout << "YES" << endl; }