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>
int n, tot, next[1111111], tail[1111111], num[1111111], bu[1111111],
    pd[1111111], sum[1111111], l[1111111], fa[1111111], oneline[1111111];
int main() {
  scanf("%d", &n);
  for (tot = 1; tot <= n; tot++) tail[tot] = tot;
  for (int i = 1; i < n; i++) {
    int t1, t2;
    scanf("%d%d", &t1, &t2);
    num[tail[t1] = next[tail[t1]] = ++tot] = t2;
    ;
    num[tail[t2] = next[tail[t2]] = ++tot] = t1;
    ;
    bu[t1]++;
    bu[t2]++;
  }
  l[1] = fa[1] = 1;
  int t = 1, w = 1;
  for (; t <= w; t++)
    for (int i = next[l[t]]; i; i = next[i])
      if (!fa[num[i]]) fa[l[++w] = num[i]] = l[t];
  for (int q = w; q; q--) {
    int i = l[q];
    if (sum[i] > 2) {
    End:;
      printf("No\n");
      return 0;
    }
    if (sum[i] == 0)
      if (bu[i] > 3 || pd[i]) sum[i] = 1;
    if (sum[i] == 2 && i - 1) oneline[fa[i]] = 3;
    if (oneline[i] && i - 1) oneline[fa[i]] = 2;
    if (oneline[i]) {
      if (bu[i] > oneline[i]) goto End;
      if (pd[i]) goto End;
    }
    if (i - 1) sum[fa[i]] += sum[i];
    if (sum[i] == 0 && bu[i] > 2 && i - 1) pd[fa[i]]++;
  }
  printf("Yes\n");
}
