import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Gen {

	static int done = 0, donePrelim = 0;

	static final Random rand = new Random(556668949239L);

	static final int maxN = 100000, maxM = 100000, max40N = 1000, max20M = 10000;

	class Edge {
		int a, b;

		public Edge(int a, int b) {
			super();
			this.a = a;
			this.b = b;
		}
	}

	class Request {
		int a, b;

		public Request(int a, int b) {
			super();
			this.a = a;
			this.b = b;
		}
	}

	static ArrayList<Edge> edges = new ArrayList<Gen.Edge>();
	static ArrayList<Request> requests = new ArrayList<Gen.Request>();

	static void print() throws IOException {
		done++;
		System.err.println(done);
		PrintWriter out;
		if (done < 10)
			out = new PrintWriter("../tests/0" + String.valueOf(done));
		else
			out = new PrintWriter("../tests/" + String.valueOf(done));

		out.println((edges.size() + 1) + " " + requests.size());
		for (Edge e : edges) {
			out.println(e.a + " " + e.b);
		}
		for (Request r : requests) {
			out.println(r.a + " " + r.b);
		}

		edges.clear();
		requests.clear();

		out.close();
	}
	
	static void printPrelim() throws IOException {
		donePrelim++;
		System.err.println(donePrelim);
		PrintWriter out;
		if (donePrelim < 10)
			out = new PrintWriter("../preliminary/0" + String.valueOf(donePrelim));
		else
			out = new PrintWriter("../preliminary/" + String.valueOf(donePrelim));

		out.println((edges.size() + 1) + " " + requests.size());
		for (Edge e : edges) {
			out.println(e.a + " " + e.b);
		}
		for (Request r : requests) {
			out.println(r.a + " " + r.b);
		}

		edges.clear();
		requests.clear();

		out.close();
	}

	void genSample() {
		edges.add(new Edge(1, 2));
		edges.add(new Edge(3, 2));
		edges.add(new Edge(4, 2));
		edges.add(new Edge(2, 5));
		edges.add(new Edge(5, 6));

		requests.add(new Request(1, 5));
		requests.add(new Request(4, 6));
		requests.add(new Request(5, 6));
		requests.add(new Request(6, 3));
	}

	void genRandomTree(int n) {
		for (int i = 2; i <= n; i++) {
			int a = rand.nextInt(i - 1) + 1;
			if (rand.nextBoolean()) {
				edges.add(new Edge(a, i));
			} else {
				edges.add(new Edge(i, a));
			}
		}
	}

	void genFullTree(int k, int n) {
		int start = 1;
		int cur = k;
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < cur; j++) {
				edges.add(new Edge(start + 1, (start - 1) / k + 1));
				start++;
			}
			cur *= k;
		}
	}

	public void run() throws IOException {
		new File("../tests").mkdir();
		new File("../preliminary").mkdir();
		done = 0;
		//PRELIMINARY
		genSample();
		printPrelim();
		// ==============1
		// FOR 20
		edges.add(new Edge(1, 2));
		for (int i = 0; i < max20M; i++) {
			requests.add(new Request(1, 2));
		}
		print();
		// ===============1
		for (int i = 2; i <= max40N; i++) {
			edges.add(new Edge(i - 1, i));
		}
		while (requests.size() < max20M) {
			int a = rand.nextInt(max40N) + 1, b = rand.nextInt(max40N) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ===============2
		for (int i = 0; i < 8; i++) {
			genRandomTree(max40N);
			while (requests.size() < max20M) {
				int a = rand.nextInt(max40N) + 1, b = rand.nextInt(max40N) + 1;
				if (a != b) {
					requests.add(new Request(a, b));
				}
			}
			print();
		}
		// ===============10
		// #####################
		// #####################
		// #####################
		// FOR 40
		genFullTree(2, 7);
		for (int i = 1; i < (1 << 7); i++) {
			for (int j = i + 1; j < (1 << 7); j++) {
				if (rand.nextBoolean()) {
					requests.add(new Request(i, j));
				} else {
					requests.add(new Request(j, i));
				}
			}
		}
		print();
		// ===============1
		genFullTree(2, 9);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============2
		genFullTree(2, 9);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============3
		genFullTree(10, 2);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============4
		genFullTree(3, 6);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============5
		genFullTree(4, 4);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============6
		genFullTree(5, 4);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============7
		for (int i = 0; i < 3; i++) {
			genRandomTree(max40N);
			while (requests.size() < maxM) {
				int a = rand.nextInt(max40N) + 1, b = rand.nextInt(max40N) + 1;
				if (a != b) {
					requests.add(new Request(a, b));
				}
			}
			print();
		}
		// ==============10
		// ###########################
		// ###########################
		// ###########################
		// ###########################
		// ###########################
		// ###########################
		// FOR 100
		for (int i = 2; i <= maxN; i++) {
			edges.add(new Edge(i - 1, i));
		}
		while (requests.size() < maxM) {
			int a = rand.nextInt(maxN) + 1, b = rand.nextInt(maxN) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ===============1
		for (int i = 0; i < 23; i++) {
			genRandomTree(maxN);
			while (requests.size() < maxM) {
				int a = rand.nextInt(maxN) + 1, b = rand.nextInt(maxN) + 1;
				if (a != b) {
					requests.add(new Request(a, b));
				}
			}
			print();
		}
		// ==============24
		genFullTree(2, 16);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============25
		genFullTree(2, 16);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============26
		genFullTree(10, 4);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============27
		genFullTree(3, 10);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============28
		genFullTree(4, 8);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============29
		genFullTree(5, 7);
		while (requests.size() < maxM) {
			int a = rand.nextInt(edges.size() + 1) + 1, b = rand.nextInt(edges
					.size() + 1) + 1;
			if (a != b) {
				requests.add(new Request(a, b));
			}
		}
		print();
		// ==============30
	}

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