#include <iostream> #include <algorithm> #include <queue> using namespace std; constexpr int inf = 987654321; struct Edge { int dst, rev; int capa; }; class Graph { protected: int size; vector<vector<Edge>> g; public: Graph(int size) : size(size) { g.resize(size); } void add_edge(int src, int dst, int capa); int max_flow(int s, int t) { throw; } }; class Dinic : public Graph { vector<int> level, iter; void bfs(int s); int dfs(int v, int t, int flow); public: Dinic(int size) : Graph(size) {} int max_flow(int s, int t); }; void Graph::add_edge(int src, int dst, int capa) { g[src].push_back(Edge({dst, int(g[dst].size()), capa})); g[dst].push_back(Edge({src, int(g[src].size())-1, 0})); } void Dinic::bfs(int s) { level.assign(size, -1); queue<int> que; level[s] = 0; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); for(Edge& e : g[v]) { if(e.capa > 0 && level[e.dst] < 0) { level[e.dst] = level[v] + 1; que.push(e.dst); } } } } int Dinic::dfs(int v, int t, int flow) { if(v == t) { return flow; } for(int& i=iter[v], n=g[v].size(); i<n; ++i) { Edge& e = g[v][i]; if(e.capa <= 0 || level[v] >= level[e.dst]) { continue; } int d = dfs(e.dst, t, min(flow, e.capa)); if(d > 0) { e.capa -= d; g[e.dst][e.rev].capa += d; return d; } } return 0; } int Dinic::max_flow(int s, int t) { int res = 0; while(true) { bfs(s); if(level[t] < 0) { return res; } iter.assign(size, 0); int flow; while((flow = dfs(s, t, inf)) > 0) { res += flow; if(res >= inf) { return inf; } } } } int main(void) { constexpr int N = 111; int n; scanf("%d", &n); Dinic graph(n + N*N + 2); int s = n + N*N, t = s + 1; for(int i=0; i<n; ++i) { int r0, c0, r1, c1; scanf("%d%d%d%d", &r0, &c0, &r1, &c1); int x = n + r0 * N + c0, y = n + r1 * N + c1; graph.add_edge(s, i, 1); graph.add_edge(i, x, 1); graph.add_edge(i, y, 1); } for(int r=0; r<N; ++r) { for(int c=0; c<N; ++c) { int x = n + r * N + c; graph.add_edge(x, t, 1); } } int max_flow = graph.max_flow(s, t); puts(max_flow == n ? "YES" : "NO"); return 0; }