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

public class Main {

    static ArrayList<Integer> G[];
    static int[] D;
    static boolean[] F;
    static int firstfail = -1;
    
    static boolean[] dfs(int x) {
	boolean[] R = new boolean[4];
	F[x] = true;
	int cnt = 0, c2 = 0;
	R[0] = R[1] = R[2] = R[3] = true;
	for (Integer y : G[x]) {
	    if (!F[y]) {
		boolean[] C = dfs(y);
		++cnt;
		if (cnt > 1 || !C[3]) R[3] = false;
		if (cnt > 2 || !C[3]) R[2] = false;
		if (!C[2]) ++c2;
		if (c2 > 1 || !C[1]) {if (firstfail < 0) firstfail = x; R[1] = false;}
		if (c2 > 2 || !C[1]) R[0] = false;
	    }
	}
	//System.out.println(x + " " + R[0] + " " + R[1] + " " + R[2] + " " + R[3] + " " + cnt + " " + c2);
	return R;
    }

    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int R = 0;
        G = new ArrayList[n];
        D = new int[n];
        
        for (int i = 0; i < n; i++) G[i] = new ArrayList<Integer>();
        for (int i = 1; i < n; i++) {
    	    StringTokenizer t = new StringTokenizer(in.readLine());
	    int a = Integer.parseInt(t.nextToken()) - 1;
	    int b = Integer.parseInt(t.nextToken()) - 1;
	    G[b].add(a);
	    G[a].add(b);
	    D[a]++;
	    D[b]++;
	    if (D[a] > 2) R = a;
	    if (D[b] > 2) R = b;
        }
        F = new boolean[n];
        boolean res = dfs(R)[0];
        if (!res && firstfail >= 0) {
    	    //System.err.println("Failed at " + firstfail + ", recalculating");
    	    F = new boolean[n];
    	    res |= dfs(firstfail)[0];
    	} 
    	System.out.println(res ? "Yes" : "No");
    }
}
