from collections import deque class Edge: def __init__(self, to, rev, capacity): self.to = to self.rev = rev self.capacity = capacity class Dinic: def __init__(self, n): self.size = n self.graph = [[] for _ in range(n)] def add_edge(self, fr, to, cap): forward = Edge(to, len(self.graph[to]), cap) backward = Edge(fr, len(self.graph[fr]), 0) self.graph[fr].append(forward) self.graph[to].append(backward) def bfs_level(self, s, t, level): q = deque() level[:] = [-1] * self.size level[s] = 0 q.append(s) while q: v = q.popleft() for edge in self.graph[v]: if edge.capacity > 0 and level[edge.to] < 0: level[edge.to] = level[v] + 1 q.append(edge.to) if edge.to == t: return def dfs_flow(self, v, t, upTo, iter_, level): if v == t: return upTo for i in range(iter_[v], len(self.graph[v])): edge = self.graph[v][i] if edge.capacity > 0 and level[v] < level[edge.to]: d = self.dfs_flow(edge.to, t, min(upTo, edge.capacity), iter_, level) if d > 0: edge.capacity -= d self.graph[edge.to][edge.rev].capacity += d return d iter_[v] += 1 return 0 def max_flow(self, s, t): flow = 0 level = [-1] * self.size while True: self.bfs_level(s, t, level) if level[t] < 0: return flow iter_ = [0] * self.size while True: f = self.dfs_flow(s, t, float('inf'), iter_, level) if f == 0: break flow += f level = [-1] * self.size def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 matches = [] coordinates = set() for _ in range(N): r0 = int(input[idx]) c0 = int(input[idx+1]) r1 = int(input[idx+2]) c1 = int(input[idx+3]) idx +=4 a = (r0, c0) b = (r1, c1) matches.append( (a, b) ) coordinates.add(a) coordinates.add(b) if not coordinates: print("YES" if N ==0 else "NO") return coordinates = list(coordinates) coord_to_id = { (r,c): i + N +1 for i, (r,c) in enumerate(coordinates) } num_coords = len(coordinates) s = 0 t = 1 + N + num_coords size = t + 1 dinic = Dinic(size) for i in range(N): dinic.add_edge(s, i + 1, 1) for i in range(N): a, b = matches[i] node_i = i + 1 a_id = coord_to_id[a] b_id = coord_to_id[b] dinic.add_edge(node_i, a_id, 1) dinic.add_edge(node_i, b_id, 1) for coord in coordinates: c_id = coord_to_id[coord] dinic.add_edge(c_id, t, 1) max_flow_val = dinic.max_flow(s, t) print("YES" if max_flow_val == N else "NO") if __name__ == "__main__": main()