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 N;
vector<int> G[100005];
void yes() {
  cout << "Yes\n";
  exit(0);
}
bool path[100005];
void find_paths(int u, int p) {
  bool good = true;
  for (int v : G[u]) {
    if (v == p) continue;
    find_paths(v, u);
    if (!path[v]) good = false;
  }
  if (G[u].size() > 2) good = false;
  path[u] = good;
}
bool is_end[100005];
bool Try(int u, int p) {
  int bad1 = -1, bad2 = -1;
  for (int v : G[u]) {
    if (v == p) continue;
    if (path[v] || is_end[v]) continue;
    if (bad1 == -1)
      bad1 = v;
    else if (bad2 == -1) {
      if (p != -1) return false;
      bad2 = v;
    } else
      return false;
  }
  bool res = true;
  if (bad1 != -1) res &= Try(bad1, u);
  if (bad2 != -1) res &= Try(bad2, u);
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> N;
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  bool all_deg2 = true;
  int root;
  for (int i = 1; i <= N; i++)
    if (G[i].size() > 2) {
      all_deg2 = false;
      root = i;
      break;
    }
  if (all_deg2) yes();
  find_paths(root, -1);
  for (int u = 1; u <= N; u++) {
    if (G[u].size() == 3) {
      int num_bad = 0;
      for (int v : G[u])
        if (!path[v]) num_bad++;
      if (num_bad <= 1) is_end[u] = true;
    }
  }
  if (Try(root, -1)) yes();
  for (int v : G[root])
    if (!path[v])
      if (Try(v, -1)) yes();
  cout << "No\n";
}
