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;
const int MAXN = 100000;
vector<int> g[MAXN];
int N, degree[MAXN];
int good[MAXN];
void dfs(int u, int fu) {
  for (int i = 0; i < (int)g[u].size(); ++i) {
    int v = g[u][i];
    if (v == fu) continue;
    ++degree[u];
    dfs(v, u);
  }
}
bool check3(int u, int fu) {
  if (good[u] != 0) {
    if (good[u] == 1)
      return true;
    else
      return false;
  }
  int size = (int)g[u].size();
  if (size == 1) {
    good[u] = 1;
    return true;
  }
  if (size > 2) {
    good[u] = -1;
    return false;
  }
  for (int i = 0; i < size; ++i) {
    int v = g[u][i];
    if (v != fu) {
      if (check3(v, u))
        good[u] = 1;
      else
        good[u] = -1;
    }
  }
  return good[u] == 1;
}
bool check2(int u, int fu) {
  int size = (int)g[u].size();
  if (size > 3) return false;
  for (int i = 0; i < size; ++i) {
    int v = g[u][i];
    if (v == fu) continue;
    if (!check3(v, u)) return false;
  }
  return true;
}
bool check1(int u, int fu) {
  vector<int> arr;
  int size = (int)g[u].size();
  for (int i = 0; i < size; ++i) {
    int v = g[u][i];
    if (v == fu) continue;
    if (!check2(v, u)) {
      arr.push_back(v);
    }
  }
  if (arr.size() > 1) return false;
  for (int i = 0; i < (int)arr.size(); ++i) {
    int v = arr[i];
    if (!check1(v, u)) return false;
  }
  return true;
}
bool check0(int root) {
  vector<int> arr;
  int size = (int)g[root].size();
  for (int i = 0; i < size; ++i) {
    int u = g[root][i];
    if (!check2(u, root)) {
      arr.push_back(u);
    }
  }
  if (arr.size() > 2) return false;
  for (int i = 0; i < (int)arr.size(); ++i) {
    int u = arr[i];
    if (!check1(u, root)) return false;
  }
  return true;
}
bool recheck(int root) {
  vector<int> arr;
  int size = (int)g[root].size();
  if (size > 3) return false;
  for (int i = 0; i < size; ++i) {
    int u = g[root][i];
    if (!check3(u, root)) arr.push_back(u);
  }
  if (arr.size() > 1) return false;
  if (arr.size() == 0) return true;
  int opposite = arr[0];
  return check0(opposite);
}
void solve() {
  cin >> N;
  for (int i = 0; i + 1 < N; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v), g[v].push_back(u);
  }
  int maxDegree = 0, root = -1;
  for (int i = 0; i < N; ++i) {
    if (g[i].size() > maxDegree) {
      maxDegree = (int)g[i].size();
      root = i;
    }
  }
  if (maxDegree <= 2) {
    cout << "Yes" << endl;
  } else {
    dfs(root, -1);
    if (check0(root) || recheck(root))
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(16);
  solve();
  return 0;
}
