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.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
public class C {
    public static ArrayList<ArrayList<Integer>> adj;
    public static int n;
     public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // Scanner scan = new Scanner(System.in);
        // PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 
        n = Integer.parseInt(bf.readLine());
        adj = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<n; i++) adj.add(new ArrayList<Integer>());
        for(int i=0; i<n-1; i++) {
             StringTokenizer st = new StringTokenizer(bf.readLine());
             int a = Integer.parseInt(st.nextToken());
             int b = Integer.parseInt(st.nextToken());
             adj.get(a-1).add(b-1);
             adj.get(b-1).add(a-1);
        }
        int[] deleted = new int[n];
        for(int i=0; i<n; i++) {
            if(deleted[i] == -1) continue;
            if(adj.get(i).size() == 1) {
                deleted[i] = -1;
                int cur = adj.get(i).get(0);
                while(adj.get(cur).size() == 2) {
                    deleted[cur] = -1;
                    if(deleted[adj.get(cur).get(0)] == -1) cur = adj.get(cur).get(1);
                    else cur = adj.get(cur).get(0);
                }
                deleted[cur]++;
            }
        }
        for(int i=0; i<n; i++) {
            if(deleted[i] == -1) continue;
            int subcount = 0;
            for(int j : adj.get(i)) {
                if(deleted[j] == -1) continue;
                int degree = adj.get(j).size();
                if((degree - Math.min(deleted[j], 2) > 1)) subcount++;
            }
            if(subcount > 2) {
                System.out.println("No");
                System.exit(0);
            }
        }
        System.out.println("Yes");
        // StringTokenizer st = new StringTokenizer(bf.readLine());
        // int[] a = new int[n]; for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        // int n = Integer.parseInt(st.nextToken());
        // int n = scan.nextInt();
        
        // out.close(); System.exit(0);
    }
}
