import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class TestsGen {
    class Edge {
        int from, to;

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

    class Test {
        ArrayList<Edge> es = new ArrayList<Edge>();
        int[] p;
        int[] r;
        int n;
        int d;
        boolean shuffle;

        Test(int n, int d) {
            this(n, d, false);
        }

        Test(int n, int d, boolean shuffle) {
            this.n = n;
            this.d = d;
            this.shuffle = shuffle;
            es = new ArrayList<Edge>();
            p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
            r = new int[n];
        }

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

        void union(int a, int b) {
            a = get(a);
            b = get(b);
            if (a == b) {
                throw new AssertionError();
            }
            if (r[a] > r[b]) {
                p[b] = a;
            } else {
                p[a] = b;
                if (r[b] == r[a]) {
                    r[b]++;
                }
            }
        }

        void shuffle() {
            if (es.size() != n - 1) {
                throw new AssertionError("es.size() = " + es.size() + " instead of " + (n - 1));
            }
            p = null;
            r = null;
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                int x = random.nextInt(i + 1);
                a[i] = a[x];
                a[x] = i;
            }

            for (Edge e : es) {
                e.from = a[e.from];
                e.to = a[e.to];
                if (random.nextBoolean()) {
                    int tmp = e.from;
                    e.from = e.to;
                    e.to = tmp;
                }
            }
            Collections.shuffle(es, random);
        }

        void add(int x, int y) {
            Edge e = new Edge(x, y);
            union(x, y);
            es.add(e);
        }

        boolean canAdd(int x, int y) {
            return get(x) != get(y);
        }

    }

    Random random = new Random(1);

    int testCountPreliminary;
    void writePreliminary(Test t) throws IOException {
        PrintWriter pw = new PrintWriter(String.format("../preliminary/%02d", ++testCountPreliminary));
        pw.println(t.n + " " + t.d);
        if (t.es.size() != t.n - 1) {
            throw new AssertionError("t.es.size() = " + t.es.size() + " instead of " + (t.n - 1));
        }
        for (Edge e : t.es) {
            if (e.from >= t.n || e.to >= t.n) {
                throw new AssertionError();
            }
            pw.println((e.from + 1) + " " + (e.to + 1));
        }
        pw.close();
    }

    int testCount;
    void write(Test t) throws IOException {
        PrintWriter pw = new PrintWriter(String.format("../tests/%02d", ++testCount));
        pw.println(t.n + " " + t.d);
        if (t.shuffle) {
            t.shuffle();
        }
        if (t.es.size() != t.n - 1) {
            throw new AssertionError("t.es.size() = " + t.es.size() + " instead of " + (t.n - 1));
        }
        for (Edge e : t.es) {
            if (e.from >= t.n || e.to >= t.n) {
                throw new AssertionError();
            }
            pw.println((e.from + 1) + " " + (e.to + 1));
        }
        pw.close();
    }

    Test genHedgehog(int n) {
        Test t = new Test(n, 2, true);
        for (int i = 1; i < n; i++) {
            t.add(0, i);
        }
        return t;
    }

    Test genPorcupine(int n, int k) {
        n = (n - 1) / (k + 1) * (k + 1) + 1;
        Test t = new Test(n, 4, true);
        for (int i = 1; i < n; i += k + 1) {
            t.add(0, i);
            for (int j = 0; j < k; j++) {
                t.add(i, i + 1 + j);
            }
        }
        return t;
    }

    Test genStick(int n) {
        Test t = new Test(n, n / 4 * 2, true);
        for (int i = 0; i < n - 1; i++) {
            t.add(i, i + 1);
        }
        return t;
    }

    Test genRandomTree(int n, int d) {
        Test t = new Test(n, d);
        while (t.es.size() < n - 1) {
            int x, y;
            do {
                x = random.nextInt(n);
                y = random.nextInt(n);
            } while (!t.canAdd(x, y));
            t.add(x, y);
        }
        return t;
    }

    Test genKTree(int n, int k, int d) {
        Test t = new Test(n, d, true);
        ArrayList<Integer> leafs = new ArrayList<Integer>();
        for (int i = 0; i < k; i++) {
            t.add(0, i + 1);
            leafs.add(i + 1);
        }
        int it = 0;
        while (t.es.size() < n - 1) {
            int x = leafs.get(leafs.size() - 1);
            leafs.remove(leafs.size() - 1);
            for (int i = 0; i < k && t.es.size() < n - 1; i++) {
                int v = t.es.size() + 1;
                t.add(x, v);
                leafs.add(v);
            }
            if (it++ % Math.max(n / 100, 1) == 0) {
                Collections.shuffle(leafs, random);
            }
        }
        return t;
    }

    Test genKnaryTree(int n, int k, int d) {
        Test t = new Test(n, d, true);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                if (k * i + j + 1 < n) {
                    t.add(i, k * i + j + 1);
                }
            }
        }
        return t;
    }

    Test genRandWithStick(int n, int d, int stickSize) {
        Test t = new Test(n, d, true);
        for (int i = 0; i < stickSize; i++) {
            t.add(i, i + 1);
        }
        t.add(0, stickSize + 1);
        while (t.es.size() < n - 1) {
            int x, y;
            do {
                x = stickSize + random.nextInt(n - stickSize);
                y = stickSize + random.nextInt(n - stickSize);
            } while (!t.canAdd(x, y));
            t.add(x, y);
        }
        return t;
    }


    Test genStar(int n, int rays) {
        n = (n - 1) / rays * rays + 1;
        Test t = new Test(n, (n - 1) / rays * 2, true);
        for (int i = 1; i < n; i++) {
            t.add(i, Math.max(i - rays, 0));
        }
        return t;
    }

    Test genStarWithTentacles(int n, int rays, int triangleSize) {
        triangleSize = (triangleSize - 1) / rays * rays + 1;
        Test t = new Test(n, (triangleSize - 1) / rays * 2 + 2, true);
        for (int i = 1; i < triangleSize; i++) {
            t.add(i, Math.max(i - rays, 0));
        }
        //[triangleSize - rays...triangleSize)
        for (int i = triangleSize; i < n; i++) {
            t.add(i, triangleSize - rays + (i % rays));
        }
        return t;
    }

    Test genStarWithRandomTree(int n, int rays, int triangleSize, int addToD) {
        triangleSize = (triangleSize - 1) / rays * rays + 1;
        Test t = new Test(n, (triangleSize - 1) / rays * 2 + addToD, true);
        for (int i = 1; i < triangleSize; i++) {
            t.add(i, Math.max(i - rays, 0));
        }
        //[triangleSize - rays...triangleSize)
        for (int i = triangleSize; i < n; i++) {
            int x =  (triangleSize - rays) + random.nextInt(i - (triangleSize - rays));
            t.add(x, i);
        }
        return t;
    }


    Test hardTest1(int n, int k) {
        Test t = hardTest1Impl(n, k);
        t.d -= 6;
        return t;
    }

    Test hardTest1Impl(int n, int k) {
        if (k == 1) {
            Test test = new Test(n, 0);
            test.n = 1;
            return test;
        }
        Test t1 = hardTest1Impl(n, k - 1);
        if (2 * (t1.es.size() + 1) > n) {
            return t1;
        }
        int m = t1.es.size() + 1;
        ArrayList<Edge> t2e = new ArrayList<Edge>();

        for (Edge e : t1.es) {
            t2e.add(new Edge(e.from + m, e.to + m));
        }
        for (Edge e : t2e) {
            t1.add(e.from, e.to);
        }
        t1.add(0, m);
        t1.n *= 2;
        t1.d += 2;
        return t1;
    }

    Test hardTest2(int n, int k) {
        if (k == 1) {
            Test test = new Test(n, 0);
            test.n = 1;
            return test;
        }
        Test t1 = hardTest2(n, k - 1);
        if (3 * (t1.es.size() + 1) > n) {
            return t1;
        }
        int m = t1.es.size() + 1;
        ArrayList<Edge> t2e = new ArrayList<Edge>();

        for (Edge e : t1.es) {
            t2e.add(new Edge(e.from, e.to));
        }
        for (Edge e : t2e) {
            t1.add(e.from + m, e.to + m);
            t1.add(e.from + 2 * m, e.to + 2 * m);
        }
        t1.add(0, m);
        t1.add(0, 2 * m);
        t1.n *= 3;
        t1.d += 2;
        return t1;
    }

    Test preliminary1() {
        Test t = new Test(4, 2, false);
        t.add(0, 1);
        t.add(0, 2);
        t.add(0, 3);
        return t;
    }
    Test preliminary2() {
        Test t = new Test(7, 2, false);
        t.add(0, 1);
        t.add(0, 2);
        t.add(0, 3);

        t.add(4, 0);
        t.add(4, 5);
        t.add(4, 6);
        return t;
    }

    int N1 = 50;
    int N2 = 500;
    int N3 = 5000;
    int MAXN = 100000;

    public void run() throws IOException {
        writePreliminary(preliminary1());
        writePreliminary(preliminary2());
        { // 01
            write(genRandomTree(5, 2));
            write(genRandomTree(10, 2));
            write(genRandomTree(20, 4));
            write(genHedgehog(N1));
            write(genPorcupine(N1, 2));
            write(genPorcupine(N1, 5));
            write(genKTree(N1, 3, 6));
            write(genRandomTree(N1, 6));
            write(genKnaryTree(N1, 2, 6));
            write(genRandomTree(N1, 1));
        }
        { // 11
            write(genHedgehog(N2 - 1));
            write(genPorcupine(N2, 2));
            write(genPorcupine(N2, 5));
            write(genKTree(N2, 3, 8));
            write(genRandomTree(N2, (int) Math.sqrt(N2)));
            write(genRandomTree(N2, 2));
            write(genRandomTree(N2, 4));
            write(genRandomTree(N2, 6));
            write(genKnaryTree(N2, 2, 12));
            write(genRandomTree(N2, 13));
        }
        { // 21
            write(genHedgehog(N3 - 1));
            write(genPorcupine(N3, 3));
            write(genKTree(N3, 3, 10));
            write(genRandomTree(N3, (int) Math.sqrt(N3)));
            write(genRandomTree(N3, 2));
            write(genRandomTree(N3, 10));
            write(genStar(N3, (int) Math.sqrt(N3)));
            write(genKnaryTree(N3, 2, 18));
            write(genStarWithRandomTree(N3, 3, N3 / 2, 10));
            write(genRandomTree(N3, 17));
        }
        { // 31
            write(genHedgehog(MAXN));
            write(genPorcupine(MAXN, 2));
            write(genPorcupine(MAXN, 5));
            write(hardTest1(MAXN, 20));

            write(hardTest2(MAXN, 20));
            write(genRandomTree(N3, 1117));
            write(genStick(MAXN));
            write(genKTree(N3, 3, 82));
            write(genRandomTree(N3, 12));
            write(genRandomTree(N3, 52));

            write(genStar(MAXN, 3));
            write(genStar(MAXN, 5));
            write(genStar(MAXN, (int) Math.sqrt(MAXN)));
            write(genStarWithTentacles(MAXN, 3, MAXN / 2));
            write(genStarWithTentacles(MAXN, 6, MAXN / 2));

            write(genRandWithStick(MAXN, 20, MAXN / 3));
            write(genStarWithRandomTree(MAXN, 3, MAXN / 2, 2));
            write(genStarWithRandomTree(MAXN, 3, MAXN / 2, 8));
            write(genStarWithRandomTree(MAXN, 3, MAXN / 2, 10));
            write(genStarWithRandomTree(MAXN, 5, MAXN - 10000, 8));

        }


    }

    public static void main(String[] args) throws IOException {
        new TestsGen().run();
    }
}
