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;
vector<int> G[100005];
int deg[100005];
int d[100005];
bool del[100005];
void dfs(int x, int par) {
  if (x == par)
    d[x] = 0;
  else
    d[x] = d[par] + 1;
  for (int it = 0; it < (int)G[x].size(); it++) {
    int y = G[x][it];
    if (del[y]) continue;
    if (y == par) continue;
    d[y] = d[x] + 1;
    dfs(y, x);
  }
}
int main() {
  int n;
  cin >> n;
  for (int e = 0; e < n - 1; e++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  for (int x = 1; x <= n; x++) deg[x] = (int)G[x].size();
  if (*max_element(deg + 1, deg + n + 1) <= 2) {
    puts("Yes");
    return 0;
  }
  memset(del, 0, sizeof del);
  deque<int> Q;
  for (int i = 1; i <= n; i++)
    if (deg[i] == 1) {
      del[i] = true;
      int at = G[i][0], prev = i;
      while (deg[at] == 2) {
        del[at] = true;
        int p = at;
        at = G[at][0] + G[at][1] - prev;
        prev = p;
      }
    }
  vector<int> all;
  for (int x = 1; x <= n; x++)
    if (!del[x]) {
      int realdeg = 0;
      for (int it = 0; it < deg[x]; it++)
        if (!del[G[x][it]]) realdeg++;
      if (realdeg == 1 && deg[x] > 3) all.push_back(x);
    }
  if ((int)all.size() > 2) {
    puts("No");
    return 0;
  }
  int A, B;
  if ((int)all.size() == 2)
    A = all[0], B = all[1];
  else if ((int)all.size() == 1) {
    A = all[0];
    fill(d, d + n + 1, -1);
    dfs(A, A);
    B = max_element(d, d + n + 1) - d;
  } else {
    int start = -1;
    for (int i = 1; i <= n; i++)
      if (!del[i]) start = i;
    assert(start != -1);
    fill(d, d + n + 1, -1);
    dfs(start, start);
    A = max_element(d, d + n + 1) - d;
    dfs(A, A);
    B = max_element(d, d + n + 1) - d;
  }
  dfs(A, A);
  if (*max_element(d, d + n + 1) == 0) {
    puts("Yes");
    return 0;
  }
  static int dA[100005];
  memcpy(dA, d, sizeof d);
  dfs(B, B);
  static int dB[100005];
  memcpy(dB, d, sizeof d);
  for (int i = 1; i <= n; i++)
    if (!del[i]) {
      if (dA[B] != dA[i] + dB[i]) {
        if (dA[i] + dB[i] != dA[B] + 2) {
          puts("No");
          return 0;
        }
      }
    }
  puts("Yes");
}
