import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.*;

public class TestGen {

    static Random rnd = new Random(3);
    static final int MAXM = 5000;

    static class TestWriter {
        final String root;
        int tests = 0;

        TestWriter(String path) {
            File root = new File(path);
            if (!root.exists()) {
                System.err.println("Creating directory <" + path + ">");
                root.mkdirs();
            }
            this.root = path;
        }

        void write(Test t) throws FileNotFoundException {
            String testNo = String.format("%02d", ++tests);
            PrintWriter out = new PrintWriter(root + "/" + testNo);
            System.err.println("Writing test (" + root + ") #" + testNo);
            out.println(t.n + " " + t.edges.size() + " " + t.k);
            for (Edge e : t.edges) {
                out.println((e.from + 1) + " " + (e.to + 1));
            }
            out.close();
        }
    }

    static class Edge {
        int from, to;

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

    static class Test {
        Test(int n, int k, List<Edge> edges) {
            this.n = n;
            this.k = k;
            this.edges = edges;
        }

        final int n, k;
        final List<Edge> edges;
    }

    static ArrayList<Edge> randomGraph(int n, int m) {
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int a, b;
            do {
                a = rnd.nextInt(n);
                b = rnd.nextInt(n);
            } while (a >= b);
            edges.add(new Edge(a, b));
        }
        return edges;
    }

    static boolean no(int n, ArrayList<Edge> edges, int k) {
        ArrayList<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (Edge e : edges) {
            g[e.from].add(e.to);
        }

        Boolean[] win = new Boolean[n];
        for (int i = 0; i < n; i++) {
            if (g[i].size() == 0) {
                win[i] = true;
            }
        }
        win[n - 1] = false;
        for (int i = n - 1; i >= 0; i--) {
            if (win[i] == null) {
                int loseCnt = 0;
                for (Integer to : g[i]) {
                    if (!win[to]) {
                        loseCnt++;
                    }
                }
                win[i] = loseCnt <= k;
            }
        }
        return !win[0];
    }

    static int lastWithNo(int n, ArrayList<Edge> g) {
        int left = 0;
        int right = g.size() + 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (no(n, g, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    static Test withNoAnswer2(int n, int m) {
        ArrayList<Edge> edges = randomGraph(n, m);
        int k = lastWithNo(n, edges);
        return new Test(n, k, edges);
    }

    static Test withYesAnswer(int n, int m) {
        ArrayList<Edge> edges = randomGraph(n, m);
        int k = lastWithNo(n, edges) + 1;
        return new Test(n, k, edges);
    }

    static Test withNoAnswer(int n, int m, int k, double p) {
        ArrayList<Integer> goods = new ArrayList<>();
        goods.add(n - 1);
        for (int i = n - 2; i >= 1; i--) {
            if (rnd.nextDouble() < p) {
                goods.add(i);
            }
        }
        goods.add(0);
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 1; i < goods.size(); i++) {
            for (int j = 0; j < k + 1; j++) {
                edges.add(new Edge(goods.get(i), goods.get(rnd.nextInt(i))));
            }
        }
        for (int i = 0; i < m - edges.size(); i++) {
            int a, b;
            do {
                a = rnd.nextInt(n);
                b = rnd.nextInt(n);
            } while (a >= b);
            edges.add(new Edge(a, b));
        }
        return new Test(n, k, edges);
    }

    public static void main(String[] args) throws FileNotFoundException {
        final Random rnd = new Random(3);
        TestWriter tests = new TestWriter("../tests");

        tests.write(new Test(4, 2, new ArrayList<Edge>() {{
            add(new Edge(0, 1));
            add(new Edge(0, 2));
            add(new Edge(1, 3));
            add(new Edge(2, 3));
        }}));

        tests.write(withNoAnswer(5, 15, 2, 0.5));
        tests.write(withYesAnswer(3, 0));
        tests.write(withYesAnswer(5, 3));
        for (int n : new int[]{5, 10, 20, 50}) {
            for (int m : new int[]{5 * n, n * n / 2, n * n, n * n * 2, MAXM}) {
                tests.write(withYesAnswer(n, m));
            }
        }
        for (int n : new int[]{5, 10, 20, 50}) {
            for (int m : new int[]{5 * n, n * n / 2, n * n, n * n * 2, MAXM}) {
                tests.write(withNoAnswer2(n, m));
            }
        }

        {
            ArrayList<Edge> e = new ArrayList<>();
            for (int i = 0; i < MAXM - 1; i++) {
                e.add(new Edge(0, 1));
            }
            tests.write(new Test(2, MAXM, e));
            tests.write(new Test(2, MAXM - 1, e));
            tests.write(new Test(2, MAXM - 2, e));
        }

        {
            tests.write(new Test(2, MAXM, new ArrayList<Edge>()));
            tests.write(new Test(2, 0, new ArrayList<Edge>()));
        }

        {
            int n = 50;
            int m = MAXM;
            ArrayList<Edge> edges = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                edges.add(new Edge(i, i + 1));
            }
            edges.add(new Edge(10, n - 1));
            int es = edges.size();
            for (int i = 0; i < m - es; i++) {
                int from = rnd.nextInt(11);
                int to = rnd.nextInt(n - 12) + 11;
                edges.add(new Edge(from, to));
            }
            tests.write(new Test(n, 1, edges));
        }

    }
}
