Problem: There is a tree with N vertices numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.

Initially, each edge is painted blue. Takahashi will convert this blue tree into a red tree, by performing the following operation N-1 times:

* Select a simple path that consists of only blue edges, and remove one of those edges.
* Then, span a new red edge between the two endpoints of the selected path.



His objective is to obtain a tree that has a red edge connecting vertices c_i and d_i, for each i.

Determine whether this is achievable.

Constraints

* 2 ≤ N ≤ 10^5
* 1 ≤ a_i,b_i,c_i,d_i ≤ N
* a_i ≠ b_i
* c_i ≠ d_i
* Both input graphs are trees.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}


Output

Print `YES` if the objective is achievable; print `NO` otherwise.

Examples

Input

3
1 2
2 3
1 3
3 2


Output

YES


Input

5
1 2
2 3
3 4
4 5
3 4
2 4
1 4
1 5


Output

YES


Input

6
1 2
3 5
4 6
1 6
5 1
5 3
1 4
2 6
4 3
5 6


Output

NO

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Set;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            List<TaskE.Vertex> vs = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                TaskE.Vertex v = new TaskE.Vertex();
                v.index = i;
                vs.add(v);
            }
            for (int i = 0; i < n - 1; ++i) {
                TaskE.Vertex a = vs.get(in.nextInt() - 1);
                TaskE.Vertex b = vs.get(in.nextInt() - 1);
                a.blueAdj.add(b);
                b.blueAdj.add(a);
            }
            for (int i = 0; i < n - 1; ++i) {
                TaskE.Vertex a = vs.get(in.nextInt() - 1);
                TaskE.Vertex b = vs.get(in.nextInt() - 1);
                a.redAdj.add(b);
                b.redAdj.add(a);
            }
            List<TaskE.Candidate> cands = new ArrayList<>();
            for (TaskE.Vertex a : vs) {
                for (TaskE.Vertex b : a.blueAdj) {
                    if (a.index < b.index && a.redAdj.contains(b)) {
                        cands.add(new TaskE.Candidate(a, b));
                    }
                }
            }
            for (TaskE.Candidate c : cands) {
                if (!c.a.blueAdj.remove(c.b)) throw new RuntimeException();
                if (!c.b.blueAdj.remove(c.a)) throw new RuntimeException();
                if (!c.a.redAdj.remove(c.b)) throw new RuntimeException();
                if (!c.b.redAdj.remove(c.a)) throw new RuntimeException();
            }
            for (int ptr = 0; ptr < cands.size(); ++ptr) {
                TaskE.Candidate ca = cands.get(ptr);
                TaskE.Vertex a = ca.a.getRoot();
                TaskE.Vertex b = ca.b.getRoot();
                if (a.blueAdj.size() + a.redAdj.size() < b.blueAdj.size() + b.redAdj.size()) {
                    TaskE.Vertex t = a;
                    a = b;
                    b = t;
                }
                b.parent = a;
                int candsPtr = cands.size();
                for (TaskE.Vertex c : b.blueAdj) {
                    if (!a.blueAdj.add(c)) throw new RuntimeException();
                    if (!c.blueAdj.remove(b)) throw new RuntimeException();
                    if (!c.blueAdj.add(a)) throw new RuntimeException();
                    if (a.redAdj.contains(c)) {
                        cands.add(new TaskE.Candidate(a, c));
                    }
                }
                for (TaskE.Vertex c : b.redAdj) {
                    if (!a.redAdj.add(c)) throw new RuntimeException();
                    if (!c.redAdj.remove(b)) throw new RuntimeException();
                    if (!c.redAdj.add(a)) throw new RuntimeException();
                    if (a.blueAdj.contains(c)) {
                        cands.add(new TaskE.Candidate(a, c));
                    }
                }
                for (int i = candsPtr; i < cands.size(); ++i) {
                    TaskE.Candidate c = cands.get(i);
                    if (!c.a.blueAdj.remove(c.b)) throw new RuntimeException();
                    if (!c.b.blueAdj.remove(c.a)) throw new RuntimeException();
                    if (!c.a.redAdj.remove(c.b)) throw new RuntimeException();
                    if (!c.b.redAdj.remove(c.a)) throw new RuntimeException();
                }
            }
            out.println(cands.size() == n - 1 ? "YES" : "NO");
        }

        static class Vertex {
            TaskE.Vertex parent;
            int index;
            Set<TaskE.Vertex> blueAdj = new HashSet<>();
            Set<TaskE.Vertex> redAdj = new HashSet<>();

            public TaskE.Vertex getRoot() {
                if (parent == null) return this;
                parent = parent.getRoot();
                return parent;
            }

        }

        static class Candidate {
            TaskE.Vertex a;
            TaskE.Vertex b;

            public Candidate(TaskE.Vertex a, TaskE.Vertex b) {
                this.a = a;
                this.b = b;
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}