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;
struct bian_ {
  int to;
  int next;
} bian[200010] = {{0, 0}};
int First[100010] = {0};
int N;
int F[100010] = {0};
int G[100010] = {0};
int Size[100010] = {0};
int leaf = 0;
int ans = 0;
int du[100010] = {0};
void Add(int p, int q, int k) {
  bian[k].to = q;
  bian[k].next = First[p];
  First[p] = k;
  return;
}
void dfs1(int cnt, int fa) {
  int Sson = 0;
  int flag = 0;
  int SizeF = 0;
  int SizeG = 0;
  int flag2 = 1;
  for (int i = First[cnt]; i != 0; i = bian[i].next) {
    int u = bian[i].to;
    if (u == fa) continue;
    dfs1(u, cnt);
    flag = 1;
    Size[cnt] += Size[u];
    if (F[u] == 1)
      SizeF++;
    else if (G[u] == 1)
      SizeG++;
    if (Size[u] > 1) flag2 = 0;
    Sson++;
  }
  if (Size[cnt] <= 2 && flag2 == 1)
    F[cnt] = 1;
  else
    F[cnt] = 0;
  if (SizeF + SizeG == Sson && SizeG <= 1)
    G[cnt] = 1;
  else
    G[cnt] = 0;
  if (flag == 0) {
    Size[cnt] = 1;
    F[cnt] = 1;
    G[cnt] = 1;
    leaf++;
  }
  return;
}
void dfs2(int cnt, int fa) {
  int SizeF = 0, SizeG = 0, Sson = 0;
  if (cnt == 4) cnt = 4;
  for (int i = First[cnt]; i != 0; i = bian[i].next) {
    int u = bian[i].to;
    if (u == fa) {
      if (leaf - Size[cnt] <= 2 &&
          (du[u] - 1 == 0 ? 1 : du[u] - 1) == leaf - Size[cnt])
        SizeF++;
    } else {
      dfs2(u, cnt);
      if (F[u] == 1)
        SizeF++;
      else if (G[u] == 1)
        SizeG++;
    }
    Sson++;
  }
  if (Sson == SizeF + SizeG && SizeG <= 2) ans = 1;
  return;
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i < N; i++) {
    int p, q;
    scanf("%d%d", &p, &q);
    Add(p, q, (i << 1) - 1);
    Add(q, p, i << 1);
    du[p]++, du[q]++;
  }
  dfs1(1, 0);
  if (du[1] == 1) leaf++;
  dfs2(1, 0);
  if (ans == 0)
    puts("No");
  else
    puts("Yes");
  return 0;
}
