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;
int tests;
int n;
vector<int> g[1 << 20];
int timer, tin[1 << 20], tout[1 << 20];
int Q, bp;
int up[1 << 19][19];
int start;
int finish;
int dep[1 << 20];
int root;
vector<int> shit;
void dfs(int v, int p) {
  tin[v] = timer;
  timer++;
  up[v][0] = p;
  for (int i = 1; i < 19; i++) up[v][i] = up[up[v][i - 1]][i - 1];
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i];
    if (to == p) continue;
    dep[to] = dep[v] + 1;
    dfs(to, v);
  }
  tout[v] = timer;
  ++timer;
}
bool upper(int a, int b) { return (tin[a] <= tin[b] && tout[a] >= tout[b]); }
int lca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = 18; i >= 0; --i)
    if (!upper(up[a][i], b)) a = up[a][i];
  return up[a][0];
}
int get_dist(int a, int b) {
  int q = lca(a, b);
  return dep[a] + dep[b] - dep[q] * 2;
}
int broken[1 << 20], leaves[1 << 20];
void solve(int v, int par) {
  int totake = 0;
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i];
    if (to == par) continue;
    solve(to, v);
    if (broken[to] == 0) leaves[v] += leaves[to];
    if (broken[to] == 0 && leaves[to] > 1) totake = 1;
  }
  if (g[v].size() == 1) leaves[v]++;
  if (leaves[v] > 2 || totake == 1) {
    shit.push_back(v);
    broken[v] = 1;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if (n < 3) {
    cout << "Yes" << endl;
    return 0;
  }
  root = 1;
  while (g[root].size() == 1) ++root;
  dfs(root, root);
  solve(root, root);
  vector<int> v = shit;
  int bst = 1e9;
  bp = 0;
  for (int i = 0; i < v.size(); i++)
    if (tout[v[i]] < bst) bst = tout[v[i]], bp = v[i];
  start = bp;
  bst = -1e9;
  bp = 0;
  for (int i = 0; i < v.size(); i++)
    if (upper(v[i], start) == 0) {
      if (tin[v[i]] > bst) {
        bst = tin[v[i]];
        bp = v[i];
      }
    }
  if (bst < 0) {
    bst = 1e9;
    bp = 0;
    for (int i = 0; i < v.size(); i++)
      if (tin[v[i]] < bst) bst = tin[v[i]], bp = v[i];
  }
  finish = bp;
  int er = 0;
  int N = get_dist(start, finish);
  for (int i = 0; i < v.size(); i++) {
    int id = v[i];
    if (get_dist(start, id) + get_dist(id, finish) != N) er = 1;
  }
  if (er)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
  return 0;
}
