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
import java.io.BufferedInputStream;
import java.util.*;

public class EDrawing {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(new BufferedInputStream(System.in));

        int N = scanner.nextInt();
        final Graph graph = new Graph(N);

        for (int i = 0; i < N - 1; i++) {
            graph.addEdge(scanner.nextInt() - 1, scanner.nextInt() - 1);
        }
        boolean isGood = graph.solve();
        System.out.println(isGood ? "Yes" : "No");
    }
}

class Graph {
    static int CLEAN = 0;
    static int COMPRESSED = 1; // deleted node due to compression
    static int YVERTICE = 2; // a node with 1 or 2 COMPRESSED nodes and 1 edge to a CLEAN node

    int N;
    List<List<Integer>> neighbors;
    int[] status;

    public Graph(int n) {
        N = n;
        neighbors = new ArrayList<>(N);
        for (int i = 0; i < N; i++)
            neighbors.add(i, new LinkedList<>());
        status = new int[N];
    }

    public void addEdge(int x, int y) {
        neighbors.get(x).add(y);
        neighbors.get(y).add(x);
    }

    public boolean solve() {
        Arrays.fill(status, CLEAN);

        // compress long nodes first
        for (int i = 0; i < N; i++) {
            if (status[i] == CLEAN && neighbors.get(i).size() == 1) {
                compress(i);
            }
        }

        // mark Y-VERTICES
        for (int i = 0; i < N; i++) {
            if (status[i] == CLEAN && (neighbors.get(i).size() == 2 || neighbors.get(i).size() == 3)) {
                int clean = 0;
                boolean hasYAsNeighbor = false;
                for (int next : neighbors.get(i)) {
                    if (status[next] == CLEAN) {
                        clean++;
                    } else if (status[next] == YVERTICE) {
                        hasYAsNeighbor = true;
                        break;
                    }
                }
                if (clean == 1 && !hasYAsNeighbor) status[i] = YVERTICE;
            }
        }

        for (int i = 0; i < N; i++) {
            if (status[i] == CLEAN) {
                int clean = 0;
                for (int next : neighbors.get(i)) {
                    if (status[next] == CLEAN)
                        clean++;
                }

                if (clean > 2) return false;
            }
        }

        return true;
    }

    public void compress(int cur) {
        status[cur] = COMPRESSED;
        for (int next : neighbors.get(cur)) {
            if (status[next] == CLEAN && neighbors.get(next).size() == 2)
                compress(next);
        }
    }
}