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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class E
{
	public static final Random RANDOM = new Random(System.currentTimeMillis());
	private BufferedReader bufferedReader;
	private StringTokenizer stringTokenizer;
	private PrintWriter printWriter;

	public E()
	{
		this(new BufferedReader(new InputStreamReader(System.in)));
	}

	public E(BufferedReader bufferedReader)
	{
		this.bufferedReader = bufferedReader;
		this.stringTokenizer = null;
		this.printWriter = new PrintWriter(new BufferedOutputStream(System.out));
	}

	public E(String file) throws FileNotFoundException
	{
		this(new BufferedReader(new InputStreamReader(new FileInputStream(file))));
	}

	private String next() throws IOException
	{
		while ((this.stringTokenizer == null) || (!this.stringTokenizer.hasMoreTokens()))
		{
			this.stringTokenizer = new StringTokenizer(this.bufferedReader.readLine());
		}
		return stringTokenizer.nextToken();
	}

	public int nextInt() throws IOException
	{
		return Integer.parseInt(next());
	}

	public double nextDouble() throws IOException
	{
		return Double.parseDouble(next());
	}

	public long nextLong() throws IOException
	{
		return Long.parseLong(next());
	}

	public String nextLine() throws IOException
	{
		return this.bufferedReader.readLine();
	}

	public void close()
	{
		printWriter.close();
	}

	public static void main(String[] args)
	{
		E template = new E();
		try
		{
			template.solve();
		}
		catch (IOException exception)
		{
			exception.printStackTrace();
		}
		template.close();
	}

	public static void follow(List<TreeSet<Integer>> verticesConnections, int[] legs, int vertex, int vertexFrom)
	{
		TreeSet<Integer> vertexConnections = verticesConnections.get(vertex);
		if (vertexConnections.size() < 3)
		{
			verticesConnections.set(vertex, null);
			for (int vertexTo : vertexConnections)
			{
				if (vertexTo != vertexFrom)
				{
					follow(verticesConnections, legs, vertexTo, vertex);
				}
			}
		}
		else
		{
			legs[vertex] += 1;
		}
	}

	public static boolean solve(List<TreeSet<Integer>> verticesConnections)
	{
		boolean result = true;
		int[] legs = new int[verticesConnections.size()];
		for (int vertex = 0; vertex < verticesConnections.size(); vertex++)
		{
			TreeSet<Integer> vertexConnections = verticesConnections.get(vertex);
			if (vertexConnections != null && vertexConnections.size() == 1)
			{
				verticesConnections.set(vertex, null);
				follow(verticesConnections, legs, vertexConnections.first(), vertex);
			}
		}
		for (int vertex = 0; vertex < verticesConnections.size(); vertex++)
		{
			TreeSet<Integer> vertexConnections = verticesConnections.get(vertex);
			if (vertexConnections != null)
			{
				int countNeighbours = 0;
				for (int neighbour : vertexConnections)
				{
					TreeSet<Integer> vertexConnectionsNeighbour = verticesConnections.get(neighbour);
					if (vertexConnectionsNeighbour != null)
					{
						if (vertexConnectionsNeighbour.size() - Math.min(2, legs[neighbour]) > 1)
						{
							countNeighbours++;
						}
					}
				}
				result &= countNeighbours <= 2;
			}
		}
		return result;
	}

	public void solve() throws IOException
	{
		int n = nextInt();
		List<TreeSet<Integer>> verticesConnections = new ArrayList<>();
		for (int index = 0; index < n; index++)
		{
			verticesConnections.add(new TreeSet<Integer>());
		}
		for (int index = 0; index < n - 1; index++)
		{
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			verticesConnections.get(from).add(to);
			verticesConnections.get(to).add(from);
		}
		if (solve(verticesConnections))
		{
			this.printWriter.println("Yes");
		}
		else
		{
			this.printWriter.println("No");
		}
	}
}