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 BearAndDrawing
{
	public static ArrayList<Integer>[] adj;
	public static int root;
	public static boolean result;
	
	public static void main(String[] args) throws Exception
	{
		FastScanner in = new FastScanner(System.in);
		
		int n = in.nextInt();
		
		adj = new ArrayList[n];
		for(int i = 0; i < adj.length; i++)
		{
			adj[i] = new ArrayList<Integer>();
		}
		
		for(int x = 0; x < n - 1; x++)
		{
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			
			adj[a].add(b);
			adj[b].add(a);
		}
		
		result = true;
		root = -1;
		for(int y = 0; y < adj.length; y++)
		{
			if(adj[y].size() == 1)
			{
				dfs(y, -1);
				break;
			}
		}
		
		if(root != -1)
		{
			dfs(root, -1);
		}
			
		System.out.println(result ? "Yes" : "No");
	}
	
	public static int dfs(int node, int parent)
	{
		int[] children = new int[4];
		for(int next : adj[node])
		{
			if(next != parent)
			{
				children[dfs(next, node)]++;
			}
		}
		
		if(children[3] > 0 && (children[1] > 0 || children[0] > 1 || children[2] > 0))
		{
			result = false;
		}
		else if(children[2] > 2)
		{
			result = false;
		}
		
		if(children[3] > 0 || children[2] > 1)
		{
			if(children[2] > 1 && root == -1)
			{
				root = node;
			}
			
			return 3;
		}
		else if(children[2] > 0 || children[1] > 0 || children[0] > 2)
		{
			return 2;
		}
		else if(children[0] > 1)
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
	
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream input)
		{
			br = new BufferedReader(new InputStreamReader(input));
			st = new StringTokenizer("");
		}
		
		public String next() throws IOException
		{
			if(st.hasMoreTokens())
			{
				return st.nextToken();
			}
			else
			{
				st = new StringTokenizer(br.readLine());
				return next();
			}
		}
		
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
	}
}
