Problem: My name is James diGriz, I'm the most clever robber and treasure hunter in the whole galaxy. There are books written about my adventures and songs about my operations, though you were able to catch me up in a pretty awkward moment.

I was able to hide from cameras, outsmart all the guards and pass numerous traps, but when I finally reached the treasure box and opened it, I have accidentally started the clockwork bomb! Luckily, I have met such kind of bombs before and I know that the clockwork mechanism can be stopped by connecting contacts with wires on the control panel of the bomb in a certain manner.

I see n contacts connected by n - 1 wires. Contacts are numbered with integers from 1 to n. Bomb has a security mechanism that ensures the following condition: if there exist k ≥ 2 contacts c1, c2, ..., ck forming a circuit, i. e. there exist k distinct wires between contacts c1 and c2, c2 and c3, ..., ck and c1, then the bomb immediately explodes and my story ends here. In particular, if two contacts are connected by more than one wire they form a circuit of length 2. It is also prohibited to connect a contact with itself.

On the other hand, if I disconnect more than one wire (i. e. at some moment there will be no more than n - 2 wires in the scheme) then the other security check fails and the bomb also explodes. So, the only thing I can do is to unplug some wire and plug it into a new place ensuring the fact that no circuits appear.

I know how I should put the wires in order to stop the clockwork. But my time is running out! Help me get out of this alive: find the sequence of operations each of which consists of unplugging some wire and putting it into another place so that the bomb is defused. 

Input

The first line of the input contains n (2 ≤ n ≤ 500 000), the number of contacts.

Each of the following n - 1 lines contains two of integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi) denoting the contacts currently connected by the i-th wire.

The remaining n - 1 lines contain the description of the sought scheme in the same format.

It is guaranteed that the starting and the ending schemes are correct (i. e. do not contain cicuits nor wires connecting contact with itself).

Output

The first line should contain k (k ≥ 0) — the minimum number of moves of unplugging and plugging back some wire required to defuse the bomb.

In each of the following k lines output four integers ai, bi, ci, di meaning that on the i-th step it is neccesary to unplug the wire connecting the contacts ai and bi and plug it to the contacts ci and di. Of course the wire connecting contacts ai and bi should be present in the scheme.

If there is no correct sequence transforming the existing scheme into the sought one, output -1.

Examples

Input

3
1 2
2 3
1 3
3 2


Output

1
1 2 1 3


Input

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


Output

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

Note

Picture with the clarification for the sample tests:

<image>

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Set;
import java.io.IOException;
import java.util.HashSet;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            EClockworkBomb solver = new EClockworkBomb();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class EClockworkBomb {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int[][] old = new int[2][n - 1];
            int[][] right = new int[2][n - 1];


            Set<Long> oldSet = new HashSet<>();
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < 2; j++) {
                    old[j][i] = in.readInt() - 1;
                }
                oldSet.add(key(old[0][i], old[1][i]));
            }
            Set<Long> rightSet = new HashSet<>();
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < 2; j++) {
                    right[j][i] = in.readInt() - 1;
                }
                rightSet.add(key(right[0][i], right[1][i]));
            }
            Set<Long> addSet = new HashSet<>();
            for (Long key : rightSet) {
                if (oldSet.contains(key)) {
                    continue;
                }
                addSet.add(key);
            }

            LCTNode[] nodes = new LCTNode[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new LCTNode();
                nodes[i].id = i;
            }

            for (int i = 0; i < n - 1; i++) {
                int u = old[0][i];
                int v = old[1][i];
                LCTNode e = new LCTNode();
                e.u = u;
                e.v = v;
                e.notExist = !rightSet.contains(key(u, v));
                e.pushUp();
                LCTNode.join(nodes[u], e);
                LCTNode.join(nodes[v], e);
            }

            out.println(addSet.size());
            for (Long xy : addSet) {
                int u = DigitUtils.highBit(xy);
                int v = DigitUtils.lowBit(xy);
                LCTNode.findRoute(nodes[u], nodes[v]);
                LCTNode.splay(nodes[u]);
                LCTNode deleted = nodes[u].notExistNode;
                out.append(deleted.u + 1).append(' ').append(deleted.v + 1).append(' ').append(u + 1).append(' ').append(v + 1).println();
                LCTNode.cut(nodes[deleted.u], deleted);
                LCTNode.cut(nodes[deleted.v], deleted);
                deleted.u = u;
                deleted.v = v;
                deleted.notExist = false;
                deleted.pushUp();

                LCTNode.join(nodes[u], deleted);
                LCTNode.join(nodes[v], deleted);
            }
        }

        public long key(int a, int b) {
            if (a > b) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            return DigitUtils.asLong(a, b);
        }

    }

    static class LCTNode {
        public static final LCTNode NIL = new LCTNode();
        LCTNode left = NIL;
        LCTNode right = NIL;
        LCTNode father = NIL;
        LCTNode treeFather = NIL;
        boolean reverse;
        int id;
        boolean notExist;
        LCTNode notExistNode;
        int u;
        int v;

        static {
            NIL.left = NIL;
            NIL.right = NIL;
            NIL.father = NIL;
            NIL.treeFather = NIL;
        }

        public static void access(LCTNode x) {
            LCTNode last = NIL;
            while (x != NIL) {
                splay(x);
                x.right.father = NIL;
                x.right.treeFather = x;
                x.setRight(last);
                x.pushUp();

                last = x;
                x = x.treeFather;
            }
        }

        public static void makeRoot(LCTNode x) {
            access(x);
            splay(x);
            x.reverse();
        }

        public static void cut(LCTNode y, LCTNode x) {
            makeRoot(y);
            access(x);
            splay(y);
            y.right.treeFather = NIL;
            y.right.father = NIL;
            y.setRight(NIL);
            y.pushUp();
        }

        public static void join(LCTNode y, LCTNode x) {
            makeRoot(x);
            x.treeFather = y;
        }

        public static void findRoute(LCTNode x, LCTNode y) {
            makeRoot(y);
            access(x);
        }

        public static void splay(LCTNode x) {
            if (x == NIL) {
                return;
            }
            LCTNode y, z;
            while ((y = x.father) != NIL) {
                if ((z = y.father) == NIL) {
                    y.pushDown();
                    x.pushDown();
                    if (x == y.left) {
                        zig(x);
                    } else {
                        zag(x);
                    }
                } else {
                    z.pushDown();
                    y.pushDown();
                    x.pushDown();
                    if (x == y.left) {
                        if (y == z.left) {
                            zig(y);
                            zig(x);
                        } else {
                            zig(x);
                            zag(x);
                        }
                    } else {
                        if (y == z.left) {
                            zag(x);
                            zig(x);
                        } else {
                            zag(y);
                            zag(x);
                        }
                    }
                }
            }

            x.pushDown();
            x.pushUp();
        }

        public static void zig(LCTNode x) {
            LCTNode y = x.father;
            LCTNode z = y.father;
            LCTNode b = x.right;

            y.setLeft(b);
            x.setRight(y);
            z.changeChild(y, x);

            y.pushUp();
        }

        public static void zag(LCTNode x) {
            LCTNode y = x.father;
            LCTNode z = y.father;
            LCTNode b = x.left;

            y.setRight(b);
            x.setLeft(y);
            z.changeChild(y, x);

            y.pushUp();
        }

        public String toString() {
            return "" + id;
        }

        public void pushDown() {
            if (this == NIL) {
                return;
            }
            if (reverse) {
                reverse = false;

                LCTNode tmpNode = left;
                left = right;
                right = tmpNode;

                left.reverse();
                right.reverse();
            }

            left.treeFather = treeFather;
            right.treeFather = treeFather;
        }

        public void reverse() {
            reverse = !reverse;
        }

        public void setLeft(LCTNode x) {
            left = x;
            x.father = this;
        }

        public void setRight(LCTNode x) {
            right = x;
            x.father = this;
        }

        public void changeChild(LCTNode y, LCTNode x) {
            if (left == y) {
                setLeft(x);
            } else {
                setRight(x);
            }
        }

        public void pushUp() {
            if (this == NIL) {
                return;
            }
            notExistNode = null;
            if (notExist) {
                notExistNode = this;
            }
            if (notExistNode == null) {
                notExistNode = left.notExistNode;
            }
            if (notExistNode == null) {
                notExistNode = right.notExistNode;
            }
        }

    }

    static class DigitUtils {
        private static long LONG_TO_INT_MASK = (1L << 32) - 1;

        private DigitUtils() {
        }

        public static long asLong(int high, int low) {
            return (((long) high) << 32) | (((long) low) & LONG_TO_INT_MASK);
        }

        public static int highBit(long x) {
            return (int) (x >> 32);
        }

        public static int lowBit(long x) {
            return (int) x;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}