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>
const int N = 1e5 + 5, M = 2 * N;
struct edge {
  int l, to;
} e[M];
int n, i, et, he[N], d[N], g[N], qt, q[3];
bool f1[N], f2[N], flag;
int read() {
  char c = getchar();
  int k = 0;
  for (; c < 48 || c > 57; c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) k = (k << 3) + (k << 1) + c - 48;
  return k;
}
void line(int x, int y) {
  e[++et].l = he[x];
  he[x] = et;
  e[et].to = y;
}
void dfs(int x, int fa) {
  int y, yy, s = 0, k = 0;
  for (int i = he[x]; i; i = e[i].l) {
    y = e[i].to;
    if (y == fa) continue;
    dfs(yy = y, x);
    if (f1[y]) s++;
    if (!f1[y] && !f2[y]) k++;
  }
  if (d[x] == 1 || d[x] == 2 && f1[yy]) f1[x] = 1;
  if (d[x] == 3 && s == 2) f2[x] = 1;
  if (k > 2) flag = 0;
  if (k == 2 && qt <= 1) q[++qt] = x;
}
int main() {
  for (n = read(), i = 1; i < n; i++) {
    int x = read(), y = read();
    d[x]++;
    d[y]++;
    line(x, y);
    line(y, x);
  }
  d[1]++;
  flag = 1;
  dfs(1, 0);
  if (qt > 1 || !flag) goto end;
  if (qt && q[1] != 1) {
    memset(f1, 0, sizeof(f1));
    memset(f2, 0, sizeof(f2));
    qt = 0;
    int x = q[1];
    d[1]--;
    d[x]++;
    flag = 1;
    dfs(x, 0);
    if (q[1] != x || !flag) goto end;
  }
  puts("Yes");
  return 0;
end:
  puts("No");
}
