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>
bool m1;
FILE *Input = stdin, *Output = stdout;
const int maxn = 1e5 + 5;
struct Edge {
  int to, next;
  Edge(){};
  Edge(int ar1, int ar2) {
    to = ar1;
    next = ar2;
  }
} Tree_List[maxn << 1], Tree2_List[maxn << 2];
int Numt[maxn], tott, deg[maxn], totn;
int Numt2[maxn << 1], tott2, size[maxn << 1], Max_Len2;
int Start_Mark, End_Mark, All_Mark[maxn << 1];
int Start, End, All[maxn << 1], Max_Len, next[maxn];
bool Found, onLine[maxn << 1], Mark[maxn << 1];
bool m2;
void Add_Tree(int ar1, int ar2) {
  Tree_List[++tott] = Edge(ar2, Numt[ar1]);
  Numt[ar1] = tott;
}
void Add_Tree2(int ar1, int ar2) {
  Tree2_List[++tott2] = Edge(ar2, Numt2[ar1]);
  Numt2[ar1] = tott2;
}
void Get_next(int ar1, int ar2) {
  next[ar1] = ar1;
  for (int i = Numt[ar1]; i; i = Tree_List[i].next) {
    int hh = Tree_List[i].to;
    if (hh == ar2) continue;
    Get_next(hh, ar1);
    if (deg[ar1] == 2) next[ar1] = next[hh];
  }
}
void Link(int ar1, int ar2) {
  for (int i = Numt[ar1]; i; i = Tree_List[i].next) {
    int hh = Tree_List[i].to;
    if (hh == ar2 || next[hh] == ar1) continue;
    if (deg[next[hh]] == 1 || deg[ar1] == 1) {
      Add_Tree2(ar1, next[hh]);
      Add_Tree2(next[hh], ar1);
      Link(next[hh], ar1);
    } else {
      Add_Tree2(ar1, hh);
      Add_Tree2(hh, ar1);
      Link(hh, ar1);
    }
  }
}
void Get_One_Mark(int ar1, int ar2, int ar3) {
  if (Mark[ar1] && ar3 > Max_Len) {
    Start_Mark = ar1;
    Max_Len = ar3;
  }
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_One_Mark(hh, ar1, ar3 + 1);
  }
}
void Get_the_Other_Mark(int ar1, int ar2, int ar3) {
  if (Mark[ar1] && ar3 > Max_Len) {
    End_Mark = ar1;
    Max_Len = ar3;
  }
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_the_Other_Mark(hh, ar1, ar3 + 1);
  }
}
void Get_One(int ar1, int ar2, int ar3) {
  if (ar3 > Max_Len) {
    Start = ar1;
    Max_Len = ar3;
  }
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_One(hh, ar1, ar3 + 1);
  }
}
void Get_the_Other(int ar1, int ar2, int ar3) {
  if (ar3 > Max_Len) {
    End = ar1;
    Max_Len = ar3;
  }
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_the_Other(hh, ar1, ar3 + 1);
  }
}
void Get_All(int ar1, int ar2, int ar3) {
  All[++All[0]] = ar1;
  if (ar1 == ar3) {
    Found = 1;
    return;
  }
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_All(hh, ar1, ar3);
    if (Found) return;
  }
  All[0]--;
}
void Get_All_Mark(int ar1, int ar2, int ar3) {
  if (Mark[ar1]) All[++All[0]] = ar1;
  if (ar1 == ar3) {
    Found = 1;
    return;
  }
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_All_Mark(hh, ar1, ar3);
    if (Found) return;
  }
  if (Mark[ar1]) All[0]--;
}
void Get_Two(int ar1, int ar2, int ar3) {
  if (ar3 > Max_Len) {
    Max_Len2 = Max_Len;
    End = Start;
    Max_Len = ar3;
    Start = ar1;
  } else if (ar3 > Max_Len2) {
    Max_Len2 = ar3;
    End = ar1;
  }
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_Two(hh, ar1, ar3 + 1);
  }
}
void Get_size(int ar1, int ar2) {
  size[ar1] = 1;
  for (int i = Numt2[ar1]; i; i = Tree2_List[i].next) {
    int hh = Tree2_List[i].to;
    if (hh == ar2) continue;
    Get_size(hh, ar1);
    size[ar1] += size[hh];
  }
}
int main() {
  int n;
  while (fscanf(Input, "%d", &n) == 1) {
    memset(Numt, 0, sizeof(Numt));
    memset(Numt2, 0, sizeof(Numt2));
    memset(deg, 0, sizeof(deg));
    memset(Mark, 0, sizeof(Mark));
    memset(onLine, 0, sizeof(onLine));
    tott = 0;
    totn = n;
    tott2 = 0;
    for (int i = 1; i < n; i++) {
      int h1, h2;
      fscanf(Input, "%d %d", &h1, &h2);
      Add_Tree(h1, h2);
      Add_Tree(h2, h1);
      deg[h1]++;
      deg[h2]++;
    }
    int Root = 1;
    while (Root <= n && deg[Root] == 2) Root++;
    if (Root > n) abort();
    Get_next(Root, 0);
    Link(Root, 0);
    bool Could = 1;
    Max_Len = 0;
    Get_One(Root, 0, 0);
    Max_Len = 0;
    Get_the_Other(Start, 0, 0);
    Found = All[0] = 0;
    Get_All(Start, 0, End);
    for (int i = 1; i <= All[0]; i++) onLine[All[i]] = 1;
    for (int i = 1; i <= All[0]; i++) {
      bool flag = 0;
      for (int j = Numt2[All[i]]; j; j = Tree2_List[j].next) {
        int hh = Tree2_List[j].to;
        if (onLine[hh]) continue;
        Get_size(hh, All[i]);
        if (size[hh] > 3) {
          flag = 1;
          break;
        }
        if (size[hh] == 2) abort();
      }
      if (flag) {
        Could = 0;
        break;
      }
    }
    if (Could)
      fprintf(Output, "Yes\n");
    else
      fprintf(Output, "No\n");
  }
  fclose(Input);
  fclose(Output);
  return 0;
}
