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

public class ForTwoPointers {
    static void generate(int a, long seed) throws IOException {
        int n = 5000;
        int m = 25000;
        Random r = new Random(seed);

        // Generate a permutation of vertices, leaving 0 and 1 untouched.
        int[] perm = new int[n];
        perm[0] = 0;
        perm[1] = 1;
        for (int i = 2; i < n; ++i) {
            int j = r.nextInt(2, i + 1);
            perm[i] = perm[j];
            perm[j] = i;
        }

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

        // First A vertices 0, 2, 3, ..., A will form a chain which will be at height 1000000
        // Vertex 1 will also be on that height
        // Then vertices A + 1 .. A + 20 will be at height 0 to be effectively discarded,
        //   but BFS will nevertheless test edges to them from first A vertices
        // The remaining vertices A + 21 ... n - 1 will be at random heights in range 1 ... 999999
        //   and will be connected to vertices A and 1.
        int[] h = new int[n];
        boolean[] used = new boolean[1000001];
        used[0] = true;
        used[1000000] = true;
        for (int i = 0; i <= a; ++i) {
            h[i] = 1000000;
        }
        for (int i = a + 21; i < n; ++i) {
            int hh;
            do {
                hh = r.nextInt(1, 1000000);
            } while (used[hh]);
            used[hh] = true;
            h[i] = hh;
        }

        try (PrintWriter out = new PrintWriter("test.in")) {
            out.println(n + " " + m);
            for (int i = 0; i < n; ++i) {
                out.print(h[invp[i]]);
                if (i + 1 == n) {
                    out.println();
                } else {
                    out.print(" ");
                }
            }

            int nEdges = 0;
            for (int i = 1; i < a; ++i) {
                ++nEdges;
                out.println((perm[i == 1 ? 0 : i] + 1) + " " + (perm[i + 1] + 1));
            }
            for (int i = a + 21; i < n; ++i) {
                nEdges += 2;
                out.println((perm[a] + 1) + " " + (perm[i] + 1));
                out.println("2 " + (perm[i] + 1));
            }
            Set<String> edgeUsed = new HashSet<>();
            while (++nEdges <= m) {
                String line;
                do {
                    int i1 = perm[r.nextInt(2, a + 1)] + 1;
                    int i2 = perm[r.nextInt(a + 1, a + 20)] + 1;
                    line = i1 + " " + i2;
                } while (edgeUsed.contains(line));
                edgeUsed.add(line);
                out.println(line);
            }
        }
    }

    static double measure() throws Exception {
        ProcessBuilder pb = new ProcessBuilder("/usr/bin/time", "-f", "%U", "./a.out");
        pb.redirectInput(new File("test.in"));
        pb.redirectOutput(ProcessBuilder.Redirect.DISCARD);
        Process p = pb.start();
        p.waitFor();
        String time = null;
        try (BufferedReader in = new BufferedReader(new InputStreamReader(p.getErrorStream()))) {
            time = in.readLine();
        }
        return Double.parseDouble(time);
    }

    public static void main(String[] args) throws Exception {
        Random random = new Random();
        double bestTime = 0;
        for (int i = 0; i < 10000; ++i) {
            int a = random.nextInt(1500, 1700);
            long seed = random.nextLong();
            generate(a, seed);
            double time = measure();
            if (time > bestTime) {
                bestTime = time;
                System.out.println("a = " + a + ", seed = " + seed + ": " + time);
            }
        }

//        generate(1600, -6780980290535286186L);
    }
}