Problem: Misha hacked the Codeforces site. Then he decided to let all the users change their handles. A user can now change his handle any number of times. But each new handle must not be equal to any handle that is already used or that was used at some point.

Misha has a list of handle change requests. After completing the requests he wants to understand the relation between the original and the new handles of the users. Help him to do that.

Input

The first line contains integer q (1 ≤ q ≤ 1000), the number of handle change requests.

Next q lines contain the descriptions of the requests, one per line.

Each query consists of two non-empty strings old and new, separated by a space. The strings consist of lowercase and uppercase Latin letters and digits. Strings old and new are distinct. The lengths of the strings do not exceed 20.

The requests are given chronologically. In other words, by the moment of a query there is a single person with handle old, and handle new is not used and has not been used by anyone.

Output

In the first line output the integer n — the number of users that changed their handles at least once.

In the next n lines print the mapping between the old and the new handles of the users. Each of them must contain two strings, old and new, separated by a space, meaning that before the user had handle old, and after all the requests are completed, his handle is new. You may output lines in any order.

Each user who changes the handle must occur exactly once in this description.

Examples

Input

5
Misha ILoveCodeforces
Vasya Petrov
Petrov VasyaPetrov123
ILoveCodeforces MikeMirzayanov
Petya Ivanov


Output

3
Petya Ivanov
Misha MikeMirzayanov
Vasya VasyaPetrov123

Solution (in JAVA):

Solution:
import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class HandlesChangeLarge {

    public static void main(String[] args) {
        new Solution().run();
    }//
//
    static class Solution {
        private void read(SolutionReader in) {
            this.n = in.readInt();
            this.changes = new String[n][2];
            for (int i = 0; i < n; ++i) {
                changes[i][0] = in.readString();
                changes[i][1] = in.readString();//
            }
        }

        int n;
        String[][] changes;

        private void process() {//
            this.oldToNew = new HashMap<>();
            Map<String, String> newToOld = new HashMap<>();

            for (String[] change : changes) {
                String oldHandle = change[0];
                String newHandle = change[1];

                String startHandle = newToOld.getOrDefault(oldHandle, oldHandle);

                oldToNew.put(startHandle, newHandle);
                newToOld.put(newHandle, startHandle);
            }
        }//

        Map<String, String> oldToNew;

        private void print(SolutionWriter out) {
            out.print(oldToNew.size()).println();

            for (Map.Entry<String, String> e : oldToNew.entrySet()) {
                out.print(e.getKey()).printSpace()
                    .print(e.getValue()).println();
            }
        }

        private static final boolean FAST_IO = false;

        private static SolutionReader createReader() {
            return (FAST_IO ? new FastReader() : new ScannerReader());
        }

        private static SolutionWriter createWriter() {
            return new SolutionPrintWriter();
        }

        void run() {
            read();
            process();
            print();
        }

        private boolean consoleIO = false;

        private SolutionReader initReader() {
            SolutionReader reader = createReader();

            try {
                reader.setInput("input.txt");
            } catch (FileNotFoundException e) {
                reader.setInput(System.in);
                consoleIO = true;
            }

            return reader;
        }

        private void read() {
            try (SolutionReader in = initReader()){
                read(in);
            } catch (IOException ignored) {

            }
        }

        private SolutionWriter initWriter() {
            SolutionWriter writer = createWriter();

            try {
                if (!consoleIO) {
                    writer.setOutput("output.txt");
                }
            } catch (IOException e) {
                consoleIO = true;
            }

            if (consoleIO) {
                writer.setOutput(System.out);
            }

            return writer;
        }

        private void print() {
            try (SolutionWriter out = initWriter()) {
                print(out);
            } catch (IOException ignored) {

            }
        }
    }

    static class Utils {
        static int[] castInt(List<Integer> list) {
            int[] array = new int[list.size()];
            for (int i = 0; i < array.length; ++i) {
                array[i] = list.get(i);
            }
            return array;
        }

        static int getBit(int mask, int bit) {
            return ((mask >> bit) & 1);
        }
    }

    interface SolutionReader extends Closeable {

        void setInput(InputStream input);
        void setInput(FileReader input);
        default void setInput(String fileName) throws FileNotFoundException {
            setInput(new FileReader(fileName));
        }

        String readLine();
        String readString();

        int readInt();
        default int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = readInt();
            }
            return a;
        }

        default int[] readIntArrayWithDecrease(int n) {
            int[] a = readIntArray(n);
            for (int i = 0; i < n; ++i) a[i]--;
            return a;
        }
    }

    static class ScannerReader implements SolutionReader {

        private Scanner in;

        @Override
        public void setInput(FileReader input) {
            this.in = new Scanner(input);
        }

        @Override
        public void setInput(InputStream input) {
            this.in = new Scanner(input);
        }

        @Override
        public String readLine() {
            String result = in.nextLine();
            if (result != null && result.isEmpty()) result = in.nextLine();
            return result;
        }

        @Override
        public String readString() {
            return in.next();
        }

        @Override
        public int readInt() {
            return in.nextInt();
        }

        @Override
        public void close() {
            in.close();
        }
    }

    static class FastReader implements SolutionReader {

        private BufferedReader in;
        private StringTokenizer tok;

        private void initTokenizer() {
            this.tok = new StringTokenizer("");
        }

        @Override
        public void setInput(FileReader input) {
            this.in = new BufferedReader(input);
            initTokenizer();
        }

        @Override
        public void setInput(InputStream input) {
            this.in = new BufferedReader(new InputStreamReader(input));
            initTokenizer();
        }

        @Override
        public String readLine() {
            try {
                return in.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        @Override
        public String readString() {
            while (!tok.hasMoreTokens()) {
                String nextLine = readLine();
                if (nextLine == null) return null;
                tok = new StringTokenizer(nextLine);
            }

            return tok.nextToken();
        }

        @Override
        public int readInt() {
            return Integer.parseInt(readString());
        }

        @Override
        public void close() throws IOException {
            in.close();
        }
    }

    interface SolutionWriter extends Closeable {

        void setOutput(PrintStream out);
        void setOutput(FileWriter out);

        default void setOutput(String fileName) throws IOException {
            setOutput(new FileWriter(fileName));
        }

        SolutionWriter println();

        SolutionWriter print(String line);
        default SolutionWriter printSpace() {
            return print(" ");
        }

        SolutionWriter print(int value);
        SolutionWriter print(long value);
        SolutionWriter print(double value);

        default SolutionWriter printAll(int... values) {
            for (int value : values) {
                print(value).printSpace();
            }
            return this;
        }

        default SolutionWriter printAll(Iterable<Integer> values) {
            for (int value : values) {
                print(value).printSpace();
            }
            return this;
        }

        default SolutionWriter printIndexes(int... indexes) {
            for (int index : indexes) {
                print(index + 1).printSpace();
            }
            return this;
        }

        default SolutionWriter printAllSeparated(int... values) {
            for (int value : values) {
                print(value).println();
            }
            return this;
        }

        default SolutionWriter printPointsSeparated(Point[] points) {
            for (Point point : points) {
                printAll(point.x, point.y).println();
            }
            return this;
        }

        default SolutionWriter printAll(long... values) {
            for (long value : values) {
                print(value).printSpace();
            }
            return this;
        }

        default SolutionWriter printAll(double... values) {
            for (double value : values) {
                print(value).printSpace();
            }
            return this;
        }
    }

    static class SolutionPrintWriter implements SolutionWriter {

        private PrintWriter out;

        @Override
        public void setOutput(PrintStream out) {
            this.out = new PrintWriter(out);
        }

        @Override
        public void setOutput(FileWriter out) {
            this.out = new PrintWriter(out);
        }

        @Override
        public SolutionWriter println() {
            out.println();
            return this;
        }

        @Override
        public SolutionWriter print(String line) {
            out.print(line);
            return this;
        }

        @Override
        public SolutionWriter print(int value) {
            out.print(value);
            return this;
        }

        @Override
        public SolutionWriter print(long value) {
            out.print(value);
            return this;
        }

        @Override
        public SolutionWriter print(double value) {
            out.printf(Locale.US, "%.12f", value);
            return this;
        }

        @Override
        public void close() {
            out.close();
        }
    }
}