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;
long long mod = 1000000007;
int main() {
  int n, m, k;
  long long ans = 0;
  scanf("%d", &n);
  std::vector<std::vector<int>> ch(n + 1);
  std::vector<int> par(n + 1);
  std::vector<std::vector<int>> nb(n + 1);
  std::vector<std::vector<int>> lvl(n + 1);
  std::vector<int> v_lvl(n + 1, 0);
  m = 1;
  lvl[1].push_back(1);
  v_lvl[1] = 1;
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    nb[u].push_back(v);
    nb[v].push_back(u);
  }
  int l = 2;
  while (m < n) {
    for (int k = 0; k < lvl[l - 1].size(); k++) {
      int v = lvl[l - 1][k];
      for (int h = 0; h < nb[v].size(); h++) {
        if (v_lvl[nb[v][h]] == 0) {
          v_lvl[nb[v][h]] = l;
          lvl[l].push_back(nb[v][h]);
          m++;
          ch[v].push_back(nb[v][h]);
          par[nb[v][h]] = v;
        }
      }
    }
    l++;
  }
  l--;
  std::vector<long long> lsize(l + 1);
  for (int i = 1; i <= l; i++) lsize[i] = lvl[i].size();
  std::vector<int> vclass(n + 1, 0);
  std::vector<int> val(n + 1, 0);
  for (int lev = l; lev >= 1; lev--) {
    for (auto v : lvl[lev]) {
      if (ch[v].size() == 0)
        vclass[v] = 0;
      else if (ch[v].size() == 1) {
        int u = ch[v][0];
        if (vclass[u] == 0)
          vclass[v] = 0;
        else if (vclass[u] == 1)
          vclass[v] = 2;
        else if (vclass[u] == 2)
          vclass[v] = 2;
        else if (vclass[u] == 3) {
          vclass[v] = 3;
          if (val[u] == 3)
            val[v] = 2;
          else
            val[v] = 1;
        }
      } else if (ch[v].size() >= 2) {
        std::vector<int> cc;
        int freeval;
        for (auto x : ch[v]) {
          cc.push_back(vclass[x]);
          if (vclass[x] == 3) freeval = val[x];
        }
        sort((cc).begin(), (cc).end());
        reverse((cc).begin(), (cc).end());
        if (cc[0] == 3) {
          if ((cc[1] > 0) || (cc.size() > 3)) {
            cout << "No";
            return 0;
          }
          vclass[v] = 3;
          val[v] = 1;
          if (freeval == 3) {
            if (cc.size() == 3) {
              if (v != 1) {
                cout << "No";
                return 0;
              }
            }
          } else {
            if (cc.size() == 3) {
              cout << "No";
              return 0;
            }
            if (v != 1) {
              cout << "No";
              return 0;
            }
          }
        } else if (cc[0] == 2) {
          if (cc[1] == 2) {
            vclass[v] = 3;
            val[v] = 3;
            if (cc.size() > 2)
              if (cc[2] == 2) {
                cout << "No";
                return 0;
              }
          } else
            vclass[v] = 2;
        } else if (cc[0] == 1)
          vclass[v] = 2;
        else {
          if (cc.size() == 2)
            vclass[v] = 1;
          else
            vclass[v] = 2;
        }
      }
    }
  }
  cout << "Yes";
}
