class DirectedGraph(): def __init__(self, N): self.N = N self.G = [[] for i in range(N)] self.rG = [[] for i in range(N)] self.order = [] self.used1 = [0] * N self.used2 = [0] * N self.group = [-1] * N self.label = 0 self.seen = [0] * N self.Edge = set() def add_edge(self, u, v): #多重辺は排除する if (u, v) not in self.Edge: self.G[u].append(v) self.rG[v].append(u) self.Edge.add((u, v)) def dfs(self, s): stack = [~s, s] while stack: u = stack.pop() if u >= 0: if self.used1[u]: continue self.used1[u] = 1 for v in self.G[u]: if self.used1[v]: continue stack.append(~v) stack.append(v) else: u = ~u if self.seen[u]: continue self.seen[u]= 1 self.order.append(u) def rdfs(self, s, num): stack = [s] while stack: u = stack.pop() if u >= 0: self.used2[u] = 1 self.group[u] = num for v in self.rG[u]: if self.used2[v]: continue stack.append(v) def scc(self): for i in range(self.N): if self.used1[i]: continue self.dfs(i) for s in reversed(self.order): if self.used2[s]: continue self.rdfs(s, self.label) self.label += 1 return self.label, self.group def construct(self): nG = [set() for _ in range(self.label)] mem = [[] for i in range(self.label)] for s in range(self.N): now = self.group[s] for u in self.G[s]: if now == self.group[u]: continue nG[now].add(self.group[u]) mem[now].append(s) return nG, mem class TwoSAT(): def __init__(self, N): self.G = DirectedGraph(2 * N) def add(self, x1, x2, f1, f2): if f1 == True and f2 == True: # ¬x1∪¬x2 # (x1⇒¬x2)∩(x2⇒¬x1) self.G.add_edge(x1, x2 + N) self.G.add_edge(x2, x1 + N) if f1 == True and f2 == False: # ¬x1∪x2 # (x1⇒x2)∩(¬x2⇒¬x1) self.G.add_edge(x1, x2) self.G.add_edge(x2 + N, x1 + N) if f1 == False and f2 == True: # x1∪¬x2 # (¬x1⇒¬x2)∩(x2⇒x1) self.G.add_edge(x1 + N, x2 + N) self.G.add_edge(x2, x1) if f1 == False and f2 == False: # x1∪x2 # (¬x1⇒x2)∩(¬x2⇒x1) self.G.add_edge(x1 + N, x2) self.G.add_edge(x2 + N, x1) def check(self): _, group = self.G.scc() for i in range(N): if group[i] == group[i + N]: return False return True N, M = map(int, input().split()) L, R = [0] * N, [0] * N for i in range(N): L[i], R[i] = map(int, input().split()) def check(L1, R1, L2, R2): if R1 < L2 or R2 < L1: return True return False TS = TwoSAT(N) for i in range(N): for j in range(i + 1, N): if not check(L[i], R[i], L[j], R[j]): TS.add(i, j, True, True) if not check(L[i], R[i], M - 1 - R[j], M - 1 - L[j]): TS.add(i, j, True, False) if not check(M - 1 - R[i], M - 1 - L[i], L[j], R[j]): TS.add(i, j, False, True) if not check(M - 1 - R[i], M - 1 - L[i], M - 1 - R[j], M - 1 - L[j]): TS.add(i, j, False, False) print("YES") if TS.check() else print("NO")