import java.io.*;
import java.util.*;

public class TestsGen {

    static class Edge {
        int from;
        int to;

        Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    static final Random RNG = new Random(1029384756);

    static class Test {
        Edge[] edges;
        int v1;
        int v2;

        Test(Edge[] edges, int v1, int v2) {
            this.edges = edges;
            this.v1 = v1;
            this.v2 = v2;
        }
    }

    static int testsCount;
    static final String TEST_FOLDER_PATH = "../tests/";

    static void printTest(Test test) {
        System.err.println(++testsCount);
        try {
            PrintWriter out = new PrintWriter(TEST_FOLDER_PATH + String.format("%02d", testsCount));
            int n = test.edges.length + 1;
            out.println(n);
            for (Edge e : test.edges) {
                out.println((e.from + 1) + " " + (e.to + 1));
            }
            out.println(test.v1 + 1 + " " + (test.v2 + 1));
            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    static Edge[] shuffleEverything(Edge[] edges) {
        int n = edges.length + 1;
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            int t = RNG.nextInt(i + 1);
            p[i] = p[t];
            p[t] = i;
        }
        Edge[] ret = new Edge[n - 1];
        for (int i = 0; i < n - 1; i++) {
            Edge e = edges[i];
            ret[i] = new Edge(p[e.from], p[e.to]);
        }
        for (int i = 1; i < n - 1; i++) {
            int j = RNG.nextInt(i + 1);
            Edge t = ret[j];
            ret[j] = ret[i];
            ret[i] = t;
        }
        return ret;
    }

    static Test shuffleTest(Test test) {
        int n = test.edges.length + 1;
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            int t = RNG.nextInt(i + 1);
            p[i] = p[t];
            p[t] = i;
        }
        Edge[] ret = new Edge[n - 1];
        for (int i = 0; i < n - 1; i++) {
            Edge e = test.edges[i];
            ret[i] = new Edge(p[e.from], p[e.to]);
        }
        for (int i = 1; i < n - 1; i++) {
            int j = RNG.nextInt(i + 1);
            Edge t = ret[j];
            ret[j] = ret[i];
            ret[i] = t;
        }
        int v = p[test.v1];
        int u = p[test.v2];
        return new Test(ret, v, u);
    }

    static Edge[] genBamboo(int n) {
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            p[i] = i - 1;
        }
        return shuffleEverything(getEdgeArray(p));
    }

    static Edge[] genBinaryTree(int n) {
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            p[i] = (i - 1) / 2;
        }
        return shuffleEverything(getEdgeArray(p));
    }

    static Edge[] genWideTree(int n) {
        final int CO = RNG.nextInt(10) + 1;
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            if (i <= CO) {
                p[i] = RNG.nextInt(i);
            } else {
                p[i] = RNG.nextInt(CO);
            }
        }
        return shuffleEverything(getEdgeArray(p));
    }

    static Edge[] genHighTree(int n) {
        final int CO = RNG.nextInt(10) + 1;
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            if (i <= CO) {
                p[i] = RNG.nextInt(i);
            } else {
                p[i] = i - RNG.nextInt(CO) - 1;
            }
        }
        return shuffleEverything(getEdgeArray(p));
    }

    static Edge[] getEdgeArray(int[] p) {
        int n = p.length;
        Edge[] ret = new Edge[n - 1];
        for (int i = 1; i < n; i++) {
            ret[i - 1] = new Edge(p[i], i);
        }
        return ret;
    }

    static Edge[] genRandomTree(int n) {
        int[] ret = new int[n];
        for (int i = 1; i < n; i++) {
            ret[i] = RNG.nextInt(i);
        }
        return shuffleEverything(getEdgeArray(ret));
    }

    static int random(int n) {
        return RNG.nextInt(n);
    }

    static int random(int l, int r) {
        return random(r - l + 1) + l;
    }

    static Test genRandomPair(Edge[] tree) {
        int n = tree.length + 1;
        int v, u;
        do {
            v = random(n);
            u = random(n);
        } while (v == u);
        return new Test(tree, v, u);
    }

    static Test genKLongPaths(int n, int k) {
        int pathLen = n / (k + 1);
        Edge[] edges = new Edge[n - 1];
        for (int e = 0; e < k; e++) {
            for (int i = 0; i + 1 < pathLen; i++) {
                edges[i + (pathLen - 1) * e] = new Edge(e * pathLen + i, e * pathLen + i + 1);
            }
        }
        DSU dsu = new DSU(n);
        int connectPathLen = Math.min(random(100) + 5, n / (k + 1) / 2);
        {
            int start = random(pathLen);
            int end = random(pathLen) + pathLen;
            for (int i = 0; i < connectPathLen; i++) {
                edges[k * (pathLen - 1) + i] = new Edge(start, k * pathLen + i);
                start = k * pathLen + i;
            }
            edges[k * (pathLen - 1) + connectPathLen] = new Edge(start, end);
        }
        for (int i = 0; i < k * (pathLen - 1) + connectPathLen + 1; i++) {
            dsu.union(edges[i].from, edges[i].to);
        }
        for (int i = k * (pathLen - 1) + connectPathLen + 1; i < edges.length; i++) {
            int v, u;
            do {
                v = random(n);
                u = random(n);
            } while (dsu.get(v) == dsu.get(u));
            edges[i] = new Edge(u, v);
            dsu.union(v, u);
        }
        int v = random(pathLen);
        int u = random(pathLen) + pathLen;
        return shuffleTest(new Test(edges, v, u));
    }

    static class DSU {
        int[] p;

        DSU(int n) {
            p = new int[n];
            for (int i = 0; i < n; i++) p[i] = i;
        }

        int get(int x) {
            return x == p[x] ? x : (p[x] = get(p[x]));
        }

        void union(int x, int y) {
            p[get(x)] = get(y);
        }
    }

    static final int MAXN = 200000;

    public static void main(String[] args) {
        printTest(new Test(new Edge[]{new Edge(0, 1), new Edge(1, 2), new Edge(2, 3), new Edge(3, 4), new Edge(4, 5)}, 3, 4));
        printTest(new Test(new Edge[]{new Edge(0, 1), new Edge(1, 2), new Edge(2, 3), new Edge(1, 4), new Edge(4, 5),
                new Edge(2, 6), new Edge(6, 7)}, 0, 7));
        for (int i = 2; i <= 6; i++) {
            printTest(genRandomPair(genRandomTree(i)));
        }
        for (int i = 0; i < 10; i++) {
            printTest(genRandomPair(genRandomTree(random(5) + 8)));
        }
        for (int i = 0; i < 5; i++) {
            printTest(genKLongPaths(random(20) + 20, i % 3 + 2));
        }
        printTest(genRandomPair(genBamboo(MAXN)));
        printTest(genRandomPair(genBamboo(MAXN)));
        printTest(genRandomPair(genRandomTree(MAXN)));
        printTest(genRandomPair(genBinaryTree(MAXN)));
        printTest(genRandomPair(genHighTree(MAXN)));
        printTest(genRandomPair(genWideTree(MAXN)));
        for (int i = 0; i < 5; i++) {
            printTest(genRandomPair(genRandomTree(40000 + random(100000))));
        }
        printTest(genKLongPaths(MAXN, 1));
        printTest(genKLongPaths(MAXN, 2));
        printTest(genKLongPaths(MAXN, 3));
        printTest(genKLongPaths(MAXN, 4));
        printTest(genKLongPaths(MAXN / 6, 2));
        printTest(genKLongPaths(MAXN / 3, 3));
        printTest(genKLongPaths(MAXN / 3, 4));
    }
}
