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 C {
	FastScanner in;
	PrintWriter out;

	ArrayList<Integer>[] g;
	boolean[] del;
	int[] leg;

	void dfs(int v, int p) {
		int deg = g[v].size() - (p != -1 ? 1 : 0);
		if (deg <= 1) {
			del[v] = true;
			for (int u : g[v]) {
				if (u != p) {
					dfs(u, v);
				}
			}
		} else {
			leg[v]++;
		}
	}

	public void solve() throws IOException {
		int n = in.nextInt();
		g = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			g[i] = new ArrayList<>();
		}
		for (int i = 0; i < n - 1; i++) {
			int a = in.nextInt() - 1, b = in.nextInt() - 1;
			g[a].add(b);
			g[b].add(a);
		}
		del = new boolean[n];
		leg = new int[n];
		for (int i = 0; i < n; i++) {
			if (g[i].size() == 1 && !del[i]) {
				dfs(i, -1);
			}
		}
		for (int v = 0; v < n; v++) {
			if (!del[v]) {
				int cnt = 0;
				for (int u : g[v]) {
					if (!del[u]) {
						if (leg[u] >= 3 || g[u].size() - leg[u] >= 2) {
							cnt++;
						}
					}
				}
				if (cnt > 2) {
					out.println("No");
					return;
				}
			}
		}
		out.println("Yes");
	}

	public void run() {
		try {
			in = new FastScanner();
			out = new PrintWriter(System.out);

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

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

	public static void main(String[] arg) {
		new C().run();
	}
}