#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef double DB; typedef pair PII; typedef vector VI; #define X first #define Y second #define pb push_back template inline void chkmin(T &x, T y) { if (y < x) x = y; } template inline void chkmax(T &x, T y) { if (x < y) x = y; } const int MN = 1005; int n; int f[MN], vis[MN], sz, cyc[MN], T; VI con[MN]; VI V; int p1, p2; int pr[MN]; int bf; void dfs(int u, int p) { int i, v; sz++; pr[u] = p; vis[u] = T; for (i = con[u].size() - 1; i >= 0; i--) { v = con[u][i]; if (vis[v] == T) { if (v != p) { if (!bf) { p1 = u; p2 = v; bf = 1; } } continue; } dfs(v, u); } } bool ddfs(int u) { int i, v, cnt(0); vis[u] = T; for (i = con[u].size() - 1; i >= 0; i--) { v = con[u][i]; if (vis[v] == T) continue; if (v == V[0]) continue; cnt++; if (!ddfs(v)) return 0; } if (cnt >= 2) return 0; return 1; } bool DFS(int u, int p) { int i, v, cnt(0); sz++; for (i = con[u].size() - 1; i >= 0; i--) { v = con[u][i]; if (cyc[v] == T) continue; if (v == p) continue; cnt++; if (!DFS(v, u)) return 0; } if (cnt >= 2) return 0; return 1; } int chk[MN][MN], VT; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); int i, j, k, tn; while (scanf("%d", &n) == 1) { memset(f, 0, sizeof f); memset(vis, 0, sizeof vis); memset(cyc, 0, sizeof cyc); T = 0; for (i = 0; i < n; i++) con[i].clear(); VT++; int flag(0); for (i = 0; i < n; i++) { scanf("%d%d", &j, &k); j--, k--; con[j].pb(k); con[k].pb(j); if (chk[j][k] == VT) { p1 = j; p2 = k; flag = 1; } chk[j][k] = chk[k][j] = VT; f[j] = k; } sz = 0; T++; bf = 0; dfs(0, -1); if (sz != n) { puts("NO"); continue; } V.clear(); if (!flag) { int u; T++; for (u = p1; u != p2; u = pr[u]) V.pb(u), cyc[u] = T; V.pb(p2), cyc[p2] = T; } else { T++; V.pb(p1); V.pb(p2); cyc[p1] = T; cyc[p2] = T; } if (V.size() > 1) { int cnt(0); int a[5]; for (i = 0; i < V.size(); i++) { sz = 0; if (!DFS(V[i], -1)) break; if (sz > 1) { a[cnt++] = V[i]; } } if (i < V.size()) { puts("NO"); continue; } if (cnt == 2 && chk[a[0]][a[1]] != VT) { puts("NO"); continue; } printf("%s\n", cnt <= 2 ? "YES" : "NO"); continue; } int cnt = 0; for (i = 0; i < con[V[0]].size(); i++) { int v = con[V[0]][i]; if (v == V[0]) continue; cnt++; } if (cnt > 2) { puts("NO"); continue; } for (i = 0; i < con[V[0]].size(); i++) { int v = con[V[0]][i]; if (v == V[0]) continue; T++; if (!ddfs(v)) break; } if (i < con[V[0]].size()) { puts("NO"); continue; } puts("YES"); } return 0; }