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>
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  explicit IntegerIterator(int value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) {}
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) {}
  std::reverse_iterator<IntegerIterator<T>> begin() const {
    return std::reverse_iterator<IntegerIterator<T>>(
        IntegerIterator<T>(begin_));
  }
  std::reverse_iterator<IntegerIterator<T>> end() const {
    return std::reverse_iterator<IntegerIterator<T>>(IntegerIterator<T>(end_));
  }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  ;
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  ;
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  ;
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  ;
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  ;
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  ;
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  ;
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  ;
  return ReversedIntegerRange<T>(from + 1, to);
}
using namespace std;
class TaskC {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n;
    vector<vector<int>> g(n);
    for (int i : range(n - 1)) {
      int x, y;
      in >> x >> y;
      --x, --y;
      g[x].push_back(y);
      g[y].push_back(x);
    }
    int root = -1;
    for (int i : range(n)) {
      if (g[i].size() > 3) {
        root = i;
        break;
      }
    }
    if (root == -1) {
      out << "Yes\n";
      return;
    }
    remove.assign(n, 0);
    canBeInCenter.assign(n, 0);
    dfs(g, root, -1);
    if (dfs2(g, root, -1, 2))
      out << "Yes\n";
    else
      out << "No\n";
  }
  vector<int> remove;
  vector<int> canBeInCenter;
  void dfs(const vector<vector<int>>& g, int v, int p) {
    int cntChildren = 0;
    int cntDeletedChildren = 0;
    for (int to : g[v]) {
      if (p == to) {
        continue;
      }
      dfs(g, to, v);
      if (remove[to]) {
        ++cntDeletedChildren;
      }
      ++cntChildren;
    }
    if (cntChildren <= 1 && cntDeletedChildren == cntChildren) {
      remove[v] = 1;
    }
    if (remove[v] || (cntChildren <= 2 && cntChildren == cntDeletedChildren)) {
      canBeInCenter[v] = 1;
    }
  }
  bool dfs2(const vector<vector<int>>& g, int v, int p, int allow) {
    int bads = 0;
    if (v == 18) {
      int x;
      x = 3;
      cerr << 1;
    }
    for (int to : g[v]) {
      if (p == to) {
        continue;
      }
      if (!canBeInCenter[to]) {
        ++bads;
      }
    }
    if (bads > allow) return false;
    for (int to : g[v]) {
      if (p == to) {
        continue;
      }
      if (!canBeInCenter[to]) {
        if (!dfs2(g, to, v, 1)) {
          return false;
        }
      }
    }
    return true;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskC solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}
