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
/*
 * @author:  Cwind
 * http://www.cnblogs.com/Cw-trip/
 */
import java.util.*;
import java.util.concurrent.PriorityBlockingQueue;
import java.awt.HeadlessException;
import java.awt.print.Printable;
import java.io.*;
import java.math.*;

public class Main {

	public static final int maxn = 100030;
	static final int maxe = 200030;

	static class Node {
		int to, next;
	};

	static Node[] es = new Node[maxe];
	static int[] head = new int[maxn];
	static int h = 0;

	static void init() {
		Arrays.fill(head, -1);
	}

	static void addedge(int from, int to) {
		es[h] = new Node();
		es[h].to = to;
		es[h].next = head[from];
		head[from] = h++;
	}

	static int[] leg = new int[maxn];
	static boolean del[] = new boolean[maxn];
	static int[] deg = new int[maxn];

	static void dfs(int v, int f) {
		del[v] = true;
		for (int i = head[v]; i != -1; i = es[i].next) {
			int u = es[i].to;
			if (u == f)
				continue;
			if (deg[u] <= 2) {
				dfs(u, v);
			} else {
				leg[u]++;
				return;
			}
		}
	}

	public static void main(String[] args) throws Exception {
		//Scanner in = new Scanner(new File(
			//	"/home/develop/eclipse_file/ACMproject/src/in"));
		// PrintWriter out=new PrintWriter(new File(
		// "/home/develop/eclipse_file/ACMproject/src/out"));
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		 Scanner in=new Scanner(new BufferedInputStream(System.in));

		init();
		int n;
		n = in.nextInt();
		for (int i = 1; i <= n - 1; i++) {
			int a, b;
			a = in.nextInt();
			b = in.nextInt();
			addedge(a, b);
			addedge(b, a);
			deg[a]++;
			deg[b]++;
		}
		for (int i = 1; i <= n; i++) {
			if (deg[i] == 1 && !del[i]) {
				dfs(i, -1);
			}
		}
		boolean ok = true;
		for (int v = 1; v <= n; v++) {
			if (!del[v]) {
				int cnt = 0;
				for (int i = head[v]; i != -1; i = es[i].next) {
					int u = es[i].to;
					if (del[u])
						continue;
					if (deg[u] - Math.min(leg[u], 2) > 1) {
						cnt++;
					}
				}
				if (cnt > 2) {
					ok = false;
					break;
				}
			}
		}
		if (ok) {
			out.println("Yes");
		} else {
			out.println("No");
		}
		in.close();
		out.close();
	}
}

                                                                                                