Limak is a little bear who learns to draw. People usually start with houses, fences and flowers but why would bears do it? Limak lives in the forest and he decides to draw a tree.

Recall that tree is a connected graph consisting of n vertices and n - 1 edges.

Limak chose a tree with n vertices. He has infinite strip of paper with two parallel rows of dots. Little bear wants to assign vertices of a tree to some n distinct dots on a paper so that edges would intersect only at their endpoints — drawn tree must be planar. Below you can see one of correct drawings for the first sample test.

<image>

Is it possible for Limak to draw chosen tree?

Input

The first line contains single integer n (1 ≤ n ≤ 105).

Next n - 1 lines contain description of a tree. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) denoting an edge between vertices ai and bi. It's guaranteed that given description forms a tree.

Output

Print "Yes" (without the quotes) if Limak can draw chosen tree. Otherwise, print "No" (without the quotes).

Examples

Input

8
1 2
1 3
1 6
6 4
6 7
6 5
7 8


Output

Yes


Input

13
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13


Output

No
#include <bits/stdc++.h>
using namespace std;
inline int ci() {
  register char ch;
  int f = 1;
  while (!isdigit(ch = getchar())) f = ch == '-' ? -1 : 1;
  register int x = ch ^ '0';
  while (isdigit(ch = getchar())) x = (x * 10) + (ch ^ '0');
  return f * x;
}
enum { N = 100023 };
struct Edge {
  int nxt, to;
} bow[N * 2];
int head[N], tot_e;
int deg[N];
inline void add(int x, int y) {
  tot_e++;
  bow[tot_e << 1] = (Edge){head[x], y};
  bow[tot_e << 1 | 1] = (Edge){head[y], x};
  head[y] = (head[x] = tot_e << 1) | 1;
  deg[x]++, deg[y]++;
}
bool vis[N];
void dfs(int u, int fa) {
  if (deg[u] >= 3) return;
  vis[u] = 1;
  for (int i = head[u]; i; i = bow[i].nxt) {
    int v = bow[i].to;
    if (v == fa) continue;
    dfs(v, u);
  }
}
int deg2[N];
int main() {
  int n = ci();
  for (register int i = (1); i <= (n - 1); i++) {
    int x = ci(), y = ci();
    add(x, y);
  }
  for (register int i = (1); i <= (n); i++)
    if (deg[i] == 1) dfs(i, 0);
  for (register int u = (1); u <= (n); u++)
    if (vis[u] == 0) {
      for (int i = head[u]; i; i = bow[i].nxt)
        if (vis[bow[i].to] == 1) deg2[u]++;
      deg2[u] = min(deg2[u], 2);
    }
  for (register int u = (1); u <= (n); u++)
    if (vis[u] == 0) {
      int cnt = 0;
      for (int i = head[u]; i; i = bow[i].nxt) {
        int v = bow[i].to;
        if (vis[v] == 0 && deg[v] - deg2[v] >= 2) cnt++;
      }
      if (cnt >= 3) {
        puts("No");
        return 0;
      }
    }
  puts("Yes");
  return 0;
}
