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 INF = 2147483647;
const long long INFL = 9223372036854775807LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;
vector<int> adj[100000 + 5];
vector<int> children[100000 + 5];
vector<int> order;
int max_state[100000 + 5];
void dfs(int cur, int parent) {
  for (int x : adj[cur]) {
    if (x != parent) {
      children[cur].push_back(x);
      dfs(x, cur);
    }
  }
  order.push_back(cur);
}
bool compare(const int& a, const int& b) { return max_state[a] < max_state[b]; }
bool check4(vector<int>& children) {
  if ((int)(children).size() == 0)
    return true;
  else if ((int)(children).size() == 1)
    return max_state[children[0]] == 4;
  else
    return false;
}
bool check3(vector<int>& children) {
  if ((int)(children).size() > 2) return false;
  return max_state[children[0]] == 4;
}
bool check2(vector<int>& children) {
  if (max_state[children[0]] < 2) return false;
  if ((int)(children).size() > 1 and max_state[children[1]] < 3) return false;
  return true;
}
bool check1(vector<int>& children) {
  if (max_state[children[0]] < 2) return false;
  if ((int)(children).size() > 1 and max_state[children[1]] < 2) return false;
  if ((int)(children).size() > 2 and max_state[children[2]] < 3) return false;
  return true;
}
int solve(int root, int n) {
  order.clear();
  for (int i = 0; i < n; i++) children[i].clear();
  dfs(root, -1);
  for (int x : order) {
    sort(children[x].begin(), children[x].end(), compare);
    if (check4(children[x]))
      max_state[x] = 4;
    else if (check3(children[x]))
      max_state[x] = 3;
    else if (check2(children[x]))
      max_state[x] = 2;
    else if (check1(children[x])) {
      if (x != root) {
        return x;
      }
      max_state[x] = 1;
    } else
      return -1;
  }
  return root;
}
int32_t main() {
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d", &u);
    ;
    scanf("%d", &v);
    ;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int root = solve(0, n);
  if (root == -1)
    cout << "No" << endl;
  else if (root != 0) {
    int root2 = solve(root, n);
    if (root2 != root)
      cout << "No" << endl;
    else
      cout << "Yes" << endl;
  } else
    cout << "Yes" << endl;
  return 0;
}
