class _csr: def __init__(self, n, edges): self.start = [0] * (n + 1) self.elist = [0] * len(edges) for v, _ in edges: self.start[v + 1] += 1 for i in range(1, n + 1): self.start[i] += self.start[i - 1] counter = self.start.copy() for v, e in edges: self.elist[counter[v]] = e counter[v] += 1 class scc_graph: """It calculates the strongly connected components of directed graphs. """ def __init__(self, n): """It creates a directed graph with n vertices and 0 edges. Constraints ----------- > 0 <= n <= 10 ** 8 Complexity ---------- > O(n) """ self.n = n self.edges = [] def add_edge(self, from_, to): """It adds a directed edge from the vertex `from_` to the vertex `to`. Constraints ----------- > 0 <= from_ < n > 0 <= to < n Complexity ---------- > O(1) amortized """ assert 0 <= from_ < self.n assert 0 <= to < self.n self.edges.append((from_, to)) def _scc_ids(self): g = _csr(self.n, self.edges) now_ord = 0 group_num = 0 visited = [] low = [0] * self.n order = [-1] * self.n ids = [0] * self.n parent = [-1] * self.n stack = [] for i in range(self.n): if order[i] == -1: stack.append(i) stack.append(i) while stack: v = stack.pop() if order[v] == -1: low[v] = order[v] = now_ord now_ord += 1 visited.append(v) for i in range(g.start[v], g.start[v + 1]): to = g.elist[i] if order[to] == -1: stack.append(to) stack.append(to) parent[to] = v else: low[v] = min(low[v], order[to]) else: if low[v] == order[v]: while True: u = visited.pop() order[u] = self.n ids[u] = group_num if u == v: break group_num += 1 if parent[v] != -1: low[parent[v]] = min(low[parent[v]], low[v]) for i, x in enumerate(ids): ids[i] = group_num - 1 - x return group_num, ids def scc(self): """It returns the list of the "list of the vertices" that satisfies the following. > Each vertex is in exactly one "list of the vertices". > Each "list of the vertices" corresponds to the vertex set of a strongly connected component. The order of the vertices in the list is undefined. > The list of "list of the vertices" are sorted in topological order, i.e., for two vertices u, v in different strongly connected components, if there is a directed path from u to v, the list contains u appears earlier than the list contains v. Complexity ---------- > O(n + m), where m is the number of added edges. """ group_num, ids = self._scc_ids() groups = [[] for _ in range(group_num)] for i, x in enumerate(ids): groups[x].append(i) return groups class two_sat: """It solves 2-SAT. For variables x[0], x[1], ..., x[n-1] and clauses with form > ((x[i] = f) or (x[j] = g)), it decides whether there is a truth assignment that satisfies all clauses. """ def __init__(self, n): """It creates a 2-SAT of n variables and 0 clauses. Constraints ----------- > 0 <= n <= 10 ** 8 Complexity ---------- > O(n) """ self.n = n self._answer = [False] * n self.scc = scc_graph(2 * n) def add_clause(self, i, f, j, g): """It adds a clause ((x[i] = f) or (x[j] = g)). Constraints ----------- > 0 <= i < n > 0 <= j < n Complexity ---------- > O(1) amortized """ assert 0 <= i < self.n assert 0 <= j < self.n self.scc.add_edge(2 * i + (f == 0), 2 * j + (g == 1)) self.scc.add_edge(2 * j + (g == 0), 2 * i + (f == 1)) def satisfiable(self): """If there is a truth assignment that satisfies all clauses, it returns `True`. Otherwise, it returns `False`. Constraints ----------- > You may call it multiple times. Complexity ---------- > O(n + m), where m is the number of added clauses. """ _, ids = self.scc._scc_ids() for i in range(self.n): if ids[2 * i] == ids[2 * i + 1]: return False self._answer[i] = (ids[2*i] < ids[2*i+1]) return True def answer(self): """It returns a truth assignment that satisfies all clauses of the last call of `satisfiable`. If we call it before calling `satisfiable` or when the last call of `satisfiable` returns `False`, it returns the list of length n with undefined elements. Complexity ---------- > O(n) """ return self._answer.copy() def main(): N, M = map(int, input().split()) LRs = [tuple(map(int, input().split())) for _ in range(N)] extended_LRs = LRs + [(M - R - 1, M - L - 1) for L, R in LRs] ts = two_sat(N) for i in range(2 * N): Li, Ri = extended_LRs[i] for j in range(i + 1, 2 * N): Lj, Rj = extended_LRs[j] if not (Ri < Lj or Rj < Li): ts.add_clause(i % N, i // N, j % N, j // N) print("YES" if ts.satisfiable() else "NO") main()