import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } int N; int[] A, B; int[][] G; int home(int u) { if (G[u].empty) { return -1; } const i = G[u][0]; return A[i] ^ B[i] ^ u; } int[] par; // 0: come back, 1: go alias Result = int[2]; Result[] dp, DP; void dfs(int u, int p) { par[u] = p; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != p) { dfs(v, u); } } // init Result[] rs; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != p) { // add dp[v] rs ~= dp[v]; } } // calc dp[u] const len = cast(int)(rs.length); dp[u][0] = (p != -1 && p == home(u)) ? 1 : 0; foreach (j; 0 .. len) { dp[u][0] &= rs[j][0]; } dp[u][1] = 1; if (len >= 1) { foreach (j; 0 .. len - 1) { dp[u][1] &= rs[j][0]; } dp[u][1] &= rs[len - 1][1]; } } void DFS(int u, int p) { // init alias Entry = Tuple!(Result, "r", int, "v"); Entry[] es; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; /* if (v != p) { // add dp[v] } */ if (v != p) { es ~= Entry(dp[v], v); } else { es ~= Entry(DP[u], -1); } } /* if (p != -1) { // add DP[u] } */ /* foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != p) { // calc DP[v], removing dp[v] } } */ const len = cast(int)(es.length); auto sums = new int[len + 1]; foreach (j; 0 .. len) { sums[j + 1] = sums[j] + es[j].r[0]; } foreach (j; 0 .. len) { const v = es[j].v; if (v != -1) { DP[v][0] = (home(u) == v) ? 1 : 0; DP[v][0] &= (sums[j] + (sums[len] - sums[j + 1]) >= len - 1) ? 1 : 0; DP[v][1] = 1; if (len - 1 >= 1) { if (j == len - 1) { DP[v][1] &= (sums[len - 2] >= len - 2) ? 1 : 0; DP[v][1] &= es[len - 2].r[1]; } else { DP[v][1] &= (sums[j] + (sums[len - 1] - sums[j + 1]) >= len - 2) ? 1 : 0; DP[v][1] &= es[len - 1].r[1]; } } } } foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != p) { DFS(v, u); } } } void main() { try { for (; ; ) { N = readInt(); A = new int[N]; B = new int[N]; foreach (i; 0 .. N - 1) { A[i] = readInt() - 1; B[i] = readInt() - 1; } G = new int[][N]; foreach (i; 0 .. N - 1) { G[A[i]] ~= i; G[B[i]] ~= i; } foreach (u; 0 .. N) { G[u].sort!((i0, i1) => ((A[i0] ^ B[i0] ^ u) < (A[i1] ^ B[i1] ^ u))); } debug { writeln("G = ", G); } const rt = 0; par = new int[N]; dp = new Result[N]; dfs(rt, -1); DP = new Result[N]; DFS(rt, -1); debug { writeln("rt = ", rt); writeln("dp = ", dp); writeln("DP = ", DP); } foreach (u; 0 .. N) { // init Result[] rs; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; /* if (v != par[u]) { // add dp[v] } */ if (v != par[u]) { rs ~= dp[v]; } else { rs ~= DP[u]; } } /* if (u != rt) { // add DP[u] } */ debug { writeln(u, ": ", rs); } // calc ans, rooted at u const len = cast(int)(rs.length); int ans = 1; if (len >= 1) { foreach (j; 0 .. len - 1) { ans &= rs[j][0]; } ans &= rs[len - 1][1]; } writeln(ans ? "Yes" : "No"); } } } catch (EOFException e) { } }