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.ArrayList;
import java.util.Scanner;

public class Main {

	private ArrayList<ArrayList<Integer>> graph;
	private boolean[] delete;
	private int[] ignorableLegs;

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		graph = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<Integer>());
		}
		delete = new boolean[N];
		ignorableLegs = new int[N];

		for (int i = 0; i < N - 1; i++) {
			int a = scanner.nextInt() - 1;
			int b = scanner.nextInt() - 1;
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		scanner.close();

		for (int i = 0; i < N; i++) {
			if (graph.get(i).size() == 1) {
				// 次数が1の頂点（葉になっている）から調べ始める
				dfs(i, -1);
			}
		}
		for (int i = 0; i < N; i++) {
			for (int v : graph.get(i)) {
				if (delete[v]) {
					// iがもつ葉の数を数えておく
					ignorableLegs[i]++;
				}
			}
		}

		// 足は2本までなら水平方向に収まるので無視できる
		for (int i = 0; i < N; i++) {
			ignorableLegs[i] = Math.min(ignorableLegs[i], 2);
		}

		for (int i = 0; i < N; i++) {
			if (delete[i]) {
				// 削除された頂点ならスルー
				continue;
			}
			int cnt = 0;
			for (int v : graph.get(i)) {
				// vの足が3本以上あるか、足以外に生えている場合は、iに対して垂直方向に収めることができない
				if (!delete[v] && graph.get(v).size() - 1 > ignorableLegs[v]) {
					cnt++;
				}

				// 垂直方向に収まらない枝が2本までなら、iの両側に置けば良いが、3本以上だと置くことができない
				if (cnt > 2) {
					System.out.println("No");
					return;
				}
			}
		}
		System.out.println("Yes");
		return;

	}

	private void dfs(int now, int from) {
		/*
		 * 葉から登って行き, 調べている頂点が葉へと続く1本道の途中であればdeleteする
		 */
		if (graph.get(now).size() > 2) {
			return;
		}

		/*
		 * 頂点の次数が2以下なら, nowはparentを除いて子を1つだけもつ頂点である. この頂点は葉につながる1直線の枝の途中なので,
		 * 消していく
		 */
		delete[now] = true;
		for (int upper : graph.get(now)) {
			if (upper != from) {
				dfs(upper, now);
			}
		}
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}