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 C implements Runnable {
	public static void main (String[] args) {new Thread(null, new C(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		int n = fs.nextInt();
		ArrayList<Integer>[] adj = new ArrayList[n];
		int[] deg = new int[n];
		for(int i = 0; i < n; i++) adj[i] = new ArrayList<>();
		for(int i = 0; i < n-1; i++) {
			int u = fs.nextInt()-1, v = fs.nextInt()-1;
			adj[u].add(v); adj[v].add(u);
			deg[u]++; deg[v]++;
		}
		boolean good = true;
		for(int i : deg) good &= i <= 2;
		if(good) {
			System.out.println("Yes");
			return;
		}
		
		boolean[] del = new boolean[n];
		ArrayDeque<Integer> leaves = new ArrayDeque<>();
		for(int i = 0; i < n; i++) if(deg[i] == 1) {
			leaves.add(i);
			del[i] = true;
		}
		
		int[] paths = new int[n];
		while(!leaves.isEmpty()) {
			int u = leaves.pollFirst();
			for(int v : adj[u]) if(!del[v]) {
				if(deg[v] <= 2) {
					del[v] = true;
					leaves.add(v);
				}
				else {
					paths[v]++;
				}
			}
		}
		
		boolean[] isMain = new boolean[n];
		for(int i = 0; i < n; i++) {
			if(del[i]) continue;
			int left = deg[i] - Math.min(paths[i], 2);
			//if he were some irrelevant kid then is leftover degree would be <= 1
			//and he would just deal with the lame paths.
			//Otherwise it's important and should be included on the main path
			//so all its kids can be dealt with
			if(left > 1) isMain[i] = true;
		}
		//non deleted nodes are as deep as possible without skipping a level
		//i.e. there can't be a nonMain node that has a main node in its subtree
		//based on how we mark nodes as deleted/not.
		
		boolean bad = false;
		for(int i = 0; i < n; i++) {
			if(!isMain[i]) continue;
			int deg2 = 0;
			for(int v : adj[i]) if(isMain[v]) {
				deg2++;
			}
			if(deg2 > 2) bad = true;
		}
		if(bad) out.println("No");
		else out.println("Yes");
		
		out.close();
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}