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 N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
struct Edge {
  int n, t;
} e[N * 2];
int h[N], edc, d[N];
void Add(int x, int y) {
  e[++edc] = (Edge){h[x], y};
  h[x] = edc;
  d[x]++;
}
bool v[N], g;
int n, c[N];
void Dfs(int x, int fa) {
  v[x] = 1;
  for (int i = h[x], y; i; i = e[i].n)
    if (d[y = e[i].t] == 2 && y != fa) Dfs(y, x);
}
int main() {
  n = read();
  g = 1;
  for (int i = 1; i < n; ++i) {
    int x = read(), y = read();
    Add(x, y);
    Add(y, x);
  }
  for (int i = 1; i <= n; ++i)
    if (d[i] == 1) Dfs(i, 0);
  for (int x = 1; x <= n; ++x)
    for (int i = h[x]; i; i = e[i].n) c[x] += v[e[i].t];
  for (int x = 1; x <= n && g; ++x) {
    if (v[x]) continue;
    int cnt = 0;
    for (int i = h[x]; i; i = e[i].n) {
      int y = e[i].t;
      if (d[y] == 2 && !c[y])
        cnt++;
      else if (d[y] == 3 && !c[y])
        cnt++;
      else if (d[y] == 3 && c[y] == 1)
        cnt++;
      else if (d[y] >= 4)
        cnt++;
    }
    if (cnt > 2) g = 0;
  }
  puts(g ? "Yes" : "No");
  return 0;
}
