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.InputStreamReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.util.HashSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Andrey Rechitsky (arechitsky@gmail.com)
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		FastPrinter out = new FastPrinter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    HashSet<Integer> [] adj;
    HashSet<Integer> [] bc;
    HashSet<Integer> [] nsbc;
    boolean []vis;
    public void solve(int testNumber, FastScanner in, FastPrinter out) {
        int n = in.nextInt();
        adj = new HashSet[n];
        bc = new HashSet[n];
        nsbc = new HashSet[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new HashSet<Integer>();
            bc[i] = new HashSet<Integer>();
            nsbc[i] = new HashSet<Integer>();
        }
        for (int i = 0; i < n - 1; i++) {
            int f = in.nextInt()-1;
            int t = in.nextInt()-1;
            adj[f].add(t);
            adj[t].add(f);
        }
        vis = new boolean[n];
        dfs1(0);
        vis = new boolean[n];
        out.printLine(dfs2(0, false, false)?"Yes":"No");
    }

    void dfs1(int x){
        vis[x] = true;
        for (int v:adj[x]){
            if (vis[v]) continue;
            dfs1(v);
            if (adj[v].size()>=4 || !bc[v].isEmpty()) bc[x].add(v);
            if (adj[v].size()>=3 || !nsbc[v].isEmpty()) nsbc[x].add(v);
            if (!nsbc[v].isEmpty()) bc[x].add(v);
        }
    }
    boolean dfs2(int x, boolean hasNode, boolean hasNSBC){
        vis[x] = true;
        if (bc[x].size()>=2+(hasNode?0:1)) return false;
        for (int v:adj[x]){
            if (vis[v]) continue;
            boolean hn = hasNode||adj[x].size()>=4 || bc[x].size()>=2 || !bc[x].isEmpty() && !bc[x].contains(v);
            hn |= nsbc[x].size()>=2 || !nsbc[x].isEmpty() && !nsbc[x].contains(v);
            hn|=hasNSBC;
            boolean hnsbc = adj[x].size()>=3;
            if (!dfs2(v, hn, hnsbc)) return false;
        }
        return true;
    }
}

class FastScanner {

    private BufferedReader reader;
    private StringTokenizer st;

    public FastScanner(InputStream stream) {
        this.reader = new BufferedReader(new InputStreamReader(stream));
        this.st = new StringTokenizer("");
    }

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

    public String next() {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(readLine());
        }
        return st.nextToken();
    }

    private String readLine() {
        try {
            String line = reader.readLine();
            if (line == null) throw new InputMismatchException();
            return line;
        } catch (IOException e) {
            throw new InputMismatchException();
        }
    }

}

class FastPrinter {
    private final PrintWriter writer;

    public FastPrinter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

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

    public void printLine(String s) {
        writer.println(s);
    }

}
