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

public class C implements Runnable {
    private static BufferedReader in;
    private static PrintWriter out;
    private static StringTokenizer st;
    private static Random rnd;

    private void solve() throws IOException {
        int verticesCount = nextInt();
        List<Integer>[] edges = new List[verticesCount];
        for (int i = 0; i < verticesCount; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < verticesCount - 1; i++) {
            int u = nextInt() - 1, v = nextInt() - 1;
            edges[u].add(v);
            edges[v].add(u);
        }
        boolean[][][] can = new boolean[verticesCount][3][3];
        boolean result = dfs(0, -1, can, edges);
        out.println(result ? "Yes" : "No");
    }

    private boolean dfs(int u, int p, boolean[][][] can, List<Integer>[] edges) {
        for (int v : edges[u]) {
            if (v != p) {
                dfs(v, u, can, edges);
            }
        }

        boolean canSomething = false;

        // 1 1
        {
            boolean canThis = true;
            int childs = 0;
            for (int v : edges[u]) {
                if (v != p) {
                    ++childs;
                    canThis &= can[v][1][1];
                }
            }
            canThis &= (childs <= 1);
            can[u][1][1] = canThis;
            canSomething |= canThis;
        }

        // 1 2
        {
            boolean canThis = true;
            int childs = 0;
            for (int v : edges[u]) {
                if (v != p) {
                    ++childs;
                    canThis &= can[v][1][1];
                }
            }
            canThis &= (childs <= 2);
            can[u][1][2] = canThis;
            canSomething |= canThis;
        }

        // 2 1
        {
            boolean canThis = true;
            int bad = 0;
            for (int v : edges[u]) {
                if (v != p) {
                    if (!can[v][1][2]) {
                        if (can[v][2][1]) {
                            ++bad;
                        } else {
                            canThis = false;
                        }
                    }
                }
            }
            canThis &= (bad <= 1);
            can[u][2][1] = canThis;
            canSomething |= canThis;
        }

        // 2 2
        {
            boolean canThis = true;
            int bad = 0;
            for (int v : edges[u]) {
                if (v != p) {
                    if (!can[v][1][2]) {
                        if (can[v][2][1]) {
                            ++bad;
                        } else {
                            canThis = false;
                        }
                    }
                }
            }
            canThis &= (bad <= 2);
            can[u][2][2] = can[u][2][0] = canThis;
            canSomething |= canThis;
        }

        // 2 0
        {
            boolean canThis = true;
            int oneSides = 0, twoSides = 0;
            for (int v : edges[u]) {
                if (v != p) {
                    if (can[v][1][1]) {
                        ++oneSides;
                    } else if (can[v][2][2]) {
                        ++twoSides;
                    } else {
                        canThis = false;
                    }
                }
            }
            canThis &= (twoSides <= 1 && oneSides + twoSides <= 3 - (p != -1 ? 1
                    : 0));
            can[u][2][0] |= canThis;
            canSomething |= canThis;
        }

        // 2 0
        {
            boolean canThis = true;
            int oneSides = 0, twoSides = 0;
            for (int v : edges[u]) {
                if (v != p) {
                    if (can[v][1][1]) {
                        ++oneSides;
                    } else if (can[v][2][0]) {
                        ++twoSides;
                    } else {
                        canThis = false;
                    }
                }
            }
            canThis &= (twoSides <= 1 && oneSides + twoSides <= 2 - (p != -1 ? 1
                    : 0));
            can[u][2][0] |= canThis;
            canSomething |= canThis;
        }

        return canSomething;
    }

    public static void main(String[] args) {
        new C().run();
    }

    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            rnd = new Random();

            solve();

            out.close();
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    private String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = in.readLine();

            if (line == null)
                return null;

            st = new StringTokenizer(line);
        }

        return st.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}