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<vector<int> > v;
void simplify(int cur, int p) {
  vector<int>::iterator it = find(v[cur].begin(), v[cur].end(), p);
  if (it != v[cur].end()) v[cur].erase(it);
  for (int i = 0; i < v[cur].size(); i++) simplify(v[cur][i], cur);
}
bool solve_halfline(int cur);
bool solve_line(int cur);
bool solve_halfplane(int cur);
bool solve_plane(int cur);
vector<int> res_halfline, res_line, res_halfplane, res_plane, res_partplane;
bool solve_halfline(int cur) {
  if (res_halfline[cur] == -1) {
    res_halfline[cur] = v[cur].size() <= 1;
    if (!v[cur].empty()) res_halfline[cur] &= solve_halfline(v[cur][0]);
  }
  return res_halfline[cur];
}
bool solve_line(int cur) {
  if (res_line[cur] == -1) {
    res_line[cur] = v[cur].size() <= 2;
    for (int i = 0; i < (v[cur].size()); i++)
      res_line[cur] &= solve_halfline(v[cur][i]);
  }
  return res_line[cur];
}
bool solve_halfplane(int cur) {
  if (res_halfplane[cur] == -1) {
    res_halfplane[cur] = true;
    int halfplane_cnt = 0;
    for (int i = 0; i < v[cur].size(); i++) {
      int to = v[cur][i];
      if (solve_line(to)) continue;
      if (solve_halfplane(to))
        halfplane_cnt++;
      else
        halfplane_cnt += 100;
    }
    res_halfplane[cur] = halfplane_cnt <= 1;
  }
  return res_halfplane[cur];
}
bool solve_partplane(int cur) {
  if (res_partplane[cur] == -1) {
    res_partplane[cur] = true;
    int cnt = 0;
    cnt = 0;
    for (int i = 0; i < v[cur].size(); i++) {
      int to = v[cur][i];
      if (solve_line(to)) continue;
      if (solve_halfplane(to))
        cnt++;
      else
        cnt += 100;
    }
    if (cnt > 2) res_partplane[cur] = false;
  }
  return res_partplane[cur];
}
bool solve_plane(int cur) {
  if (res_plane[cur] == -1) {
    res_plane[cur] = true;
    int cnt = 0;
    int halfcnt = 0;
    for (int i = 0; i < v[cur].size(); i++) {
      int to = v[cur][i];
      if (solve_halfline(to)) {
        halfcnt++;
        continue;
      }
      if (solve_plane(to))
        cnt++;
      else
        cnt += 100;
    }
    if (halfcnt > 1 || cnt > 1) {
      cnt = 0;
      halfcnt = 0;
      for (int i = 0; i < v[cur].size(); i++) {
        int to = v[cur][i];
        if (solve_halfline(to)) {
          halfcnt++;
          continue;
        }
        if (solve_partplane(to))
          cnt++;
        else
          cnt += 100;
      }
      if (halfcnt > 2 || cnt > 1) {
        cnt = 0;
        for (int i = 0; i < v[cur].size(); i++) {
          int to = v[cur][i];
          if (solve_line(to)) continue;
          if (solve_halfplane(to))
            cnt++;
          else
            cnt += 100;
        }
        if (cnt > 2) res_plane[cur] = false;
      }
    }
  }
  return res_plane[cur];
}
void print(int cur, int depth) {
  for (int i = 0; i < (depth); i++) putchar(' ');
  if (v[cur].empty())
    putchar('*');
  else
    putchar('+');
  printf("%d\n", cur + 1);
  for (int i = 0; i < (v[cur].size()); i++) print(v[cur][i], depth + 1);
  for (int i = 0; i < (depth); i++) putchar(' ');
  printf("-\n");
}
int main() {
  int n;
  scanf("%d", &n);
  v.resize(n);
  for (int i = 0; i < (n - 1); i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  int t = 0;
  simplify(t, -1);
  res_plane.resize(n, -1);
  res_partplane.resize(n, -1);
  res_halfplane.resize(n, -1);
  res_line.resize(n, -1);
  res_halfline.resize(n, -1);
  puts(solve_plane(t) ? "Yes" : "No");
  return 0;
}
