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.*;

public class C318C
{

private static StringTokenizer st;
    
    public static void nextLine(BufferedReader br) throws IOException
    {
        st = new StringTokenizer(br.readLine());
    }
    
    public static int nextInt()
    {
        return Integer.parseInt(st.nextToken());
    }
    
    public static String next()
    {
        return st.nextToken();
    }
    
    public static long nextLong()
    {
        return Long.parseLong(st.nextToken());
    }

    public static double nextDouble()
    {
        return Double.parseDouble(st.nextToken());
    }
    
    static boolean[] sp1;
    static ArrayList<Integer>[] edges;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        nextLine(br);
        int n = nextInt();
        edges = new ArrayList[n];
        for (int i = 0; i < n; i++)
        {
            edges[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n-1; i++)
        {
            nextLine(br);
            int a = nextInt() - 1;
            int b = nextInt() - 1;
            edges[a].add(b);
            edges[b].add(a);
        }
        if (n < 5)
        {
            System.out.println("Yes");
            return;
        }
        sp1 = new boolean[n];
        int[] c4 = new int[n];
        int[] c3 = new int[n];
        int[] c2 = new int[n];
        int max = 0;
        int start = -1;
        for (int i = 0; i < n; i++)
        {
            for (Integer next : edges[i])
            {
                if (edges[next].size() >= 4) c4[i]++;
                if (edges[next].size() >= 3) c3[i]++;
                if (edges[next].size() >= 2) c2[i]++;
            }
            if (c4[i] > 2)
            {
                System.out.println("No");
                return;
            }
            if (c4[i] == 2 || c3[i] >= 2 || edges[i].size() >= 4) sp1[i] = true;
            if (edges[i].size() > edges[max].size()) max = i;
            if (edges[i].size() == edges[max].size())
            {
                if (c3[i] > c3[max]) max = i;
                else if (c3[i] == c3[max] && c2[i] > c2[max]) max = i;
            }
            if (c4[i] == 2 && start == -1)
            {
                start = i;
            }
        }
        if (start != -1) max = start;
        if (dfs(max, -1, 0) != -1)
        {
            System.out.println("Yes");
        }
        else
        {
            System.out.println("No");
        }
    }
    
    public static int dfs(int pos, int prev, int type)
    {
        if (edges[pos].size() == 1)
        {
            return 3;
        }
        int besttype = 3;
        int used = 0;
        if (edges[pos].size() > 2) // we are at best type 2 if node has degree 3
        {
            besttype = 2;
        }
        if (type == 3 && besttype == 2) return -1;
        
        
        for (Integer next : edges[pos])
        {
            if (next == prev) continue;
            if (type == 3) return dfs(next, pos, 3);
            if (type == 2)
            {
                // type 2 can only have type 3 children
                if (dfs(next, pos, 3) == -1) return -1;
            }
            else if (type == 1)
            {
                if (used == 1)
                {
                    if (dfs(next, pos, 2) == -1)
                    {
                        return -1;
                    }
                }
                else if (sp1[next])
                {
                    if (used == 1) return -1;
                    if (dfs(next, pos, 1) == -1) return -1;
                    besttype = 1;
                    used++;
                }
                else
                {
                    int res = dfs(next, pos, 1);
                    if (res == -1) return -1;
                    if (res == 2) // if a node has a type 2 child, it must be at least type 1
                    {
                        besttype = 1;
                    }
                    else if (res < 2) // if a node has a type 1 child, then it used up one charge
                    {
                        besttype = 1;
                        used++;
                    }
                }
            }
            else
            {
                if (used == 2)
                {
                    if (dfs(next, pos, 2) == -1)
                    {
                        return -1;
                    }
                }
                else if (sp1[next])
                {
                    if (used == 2) return -1;
                    if (dfs(next, pos, 1) == -1) return -1;
                    used++;
                }
                else
                {
                    int res = dfs(next, pos, 1);
                    if (res == -1) return -1;
                    if (res < 2) // if root node has a type 1 child, then it used up one charge
                    {
                        used++;
                    }
                }
            }
        }
        
        return besttype;
    }

}