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

public class DoggyTestGen {

	class DSU {
		int[] parent, rank;

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

		int get(int v) {
			if (parent[v] == v) {
				return v;
			}
			return parent[v] = get(parent[v]);
		}

		boolean union(int a, int b) {
			a = get(a);
			b = get(b);
			if (a == b) {
				return false;
			}

			if (rank[a] == rank[b]) {
				rank[a]++;
			}
			if (rank[a] > rank[b]) {
				parent[b] = a;
			} else {
				parent[a] = b;
			}
			return true;
		}
	}

	class Edge {
		int from, to;

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

		public void shuffle() {
			if (rng.nextBoolean()) {
				int tmp = from;
				from = to;
				to = tmp;
			}
		}

		@Override
		public String toString() {
			return (from + 1) + " " + (to + 1);
		}
	}

	static class RandomUtils {
		static int[] randomPermutation(int size) {
			int[] a = new int[size];
			for (int i = 0; i < size; i++) {
				a[i] = i;
			}
			return shuffleArray(a);
		}

		static int randRange(int from, int to) {
			return rng.nextInt(to - from + 1) + from;
		}

		static int[] shuffleArray(int[] a) {
			int n = a.length;
			int[] res = a.clone();
			for (int i = 1; i < n; i++) {
				int id = rng.nextInt(i + 1);
				int tmp = res[id];
				res[id] = res[i];
				res[i] = tmp;
			}
			return res;
		}

		static <T> T[] shuffleArray(T[] a) {
			int n = a.length;
			T[] res = a.clone();
			for (int i = 1; i < n; i++) {
				int id = rng.nextInt(i + 1);
				T tmp = res[id];
				res[id] = res[i];
				res[i] = tmp;
			}
			return res;
		}
	}

	final static Random rng = new Random(577215664);

	public static void main(String[] args) throws Exception {
		new DoggyTestGen().generate();
	}

	PrintWriter out;
	boolean isPreliminary;
	int countTests = 0;

	private void applyRandomPerm(int n, Edge[] edges) {
		int[] perm = RandomUtils.randomPermutation(n);
		for (Edge e : edges) {
			e.from = perm[e.from];
			e.to = perm[e.to];
		}
	}

	void generate() throws Exception {
		generatePreliminary();
		generateTests();
	}

	void generatePreliminary() {
		isPreliminary = true;
		printTest(4, new Edge[] { new Edge(2, 1), new Edge(1, 3),
				new Edge(3, 2), new Edge(1, 0), new Edge(0, 2) });
	}

	void generateTests() {
		countTests = 0;
		isPreliminary = false;
		generateOneCycle();
		generateTwoCycles();
		generateThreeDisjointCycles();
		generateRest();
	}

	void addUpAllEdges(Edge[] edges, int n, int start) {
		DSU dsu = new DSU(n);
		int countComps = n;
		for (int i = 0; i < start; i++) {
			if (dsu.union(edges[i].from, edges[i].to)) {
				countComps--;
			}
		}

		while (countComps > 1) {
			int from = RandomUtils.randRange(0, n - 1);
			int to = RandomUtils.randRange(0, n - 1);
			if (dsu.union(from, to)) {
				edges[start++] = new Edge(from, to);
				countComps--;
			}
		}
	}

	void shuffleAll(Edge[] edges) {
		for (Edge e : edges) {
			e.shuffle();
		}
	}

	private void generateOneCycle() {
		{
			int n = 10;
			int cycleLen = 7;
			Edge[] edges = new Edge[n];
			for (int i = 0; i < cycleLen; i++) {
				edges[i] = new Edge(i, (i + 1) % cycleLen);
			}
			addUpAllEdges(edges, n, cycleLen);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 1000;
			int cycleLen = 81;
			Edge[] edges = new Edge[n];
			for (int i = 0; i < cycleLen; i++) {
				edges[i] = new Edge(i, (i + 1) % cycleLen);
			}
			addUpAllEdges(edges, n, cycleLen);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 20000;
			int cycleLen = 3;
			Edge[] edges = new Edge[n];
			for (int i = 0; i < cycleLen; i++) {
				edges[i] = new Edge(i, (i + 1) % cycleLen);
			}
			addUpAllEdges(edges, n, cycleLen);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 200000;
			int cycleLen = 199999;
			Edge[] edges = new Edge[n];
			for (int i = 0; i < cycleLen; i++) {
				edges[i] = new Edge(i, (i + 1) % cycleLen);
			}
			addUpAllEdges(edges, n, cycleLen);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
	}

	private void generateTwoCycles() {
		{
			int n = 7;
			int cycleLen1 = 3, cycleLen2 = 4;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}

		{
			int n = 3000;
			int cycleLen1 = 1500, cycleLen2 = 1500;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 40000;
			int cycleLen1 = 100, cycleLen2 = 99;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 198000;
			int cycleLen1 = 6, cycleLen2 = 196932;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
	}

	private void generateThreeDisjointCycles() {
		{
			int n = 20;
			int cycleLen1 = 5, cycleLen2 = 6, cycleLen3 = 6;
			Edge[] edges = new Edge[n + 2];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}
			for (int k = 0; k < cycleLen3; k++) {
				edges[tmp++] = new Edge(k + cycleLen1 + cycleLen2,
						((k + 1) % cycleLen3) + cycleLen1 + cycleLen2);
			}
			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 543;
			int cycleLen1 = 123, cycleLen2 = 123, cycleLen3 = 123;
			Edge[] edges = new Edge[n + 2];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}
			for (int k = 0; k < cycleLen3; k++) {
				edges[tmp++] = new Edge(k + cycleLen1 + cycleLen2,
						((k + 1) % cycleLen3) + cycleLen1 + cycleLen2);
			}
			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 5000;
			int cycleLen1 = 3, cycleLen2 = 3, cycleLen3 = 4950;
			Edge[] edges = new Edge[n + 2];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}
			for (int k = 0; k < cycleLen3; k++) {
				edges[tmp++] = new Edge(k + cycleLen1 + cycleLen2,
						((k + 1) % cycleLen3) + cycleLen1 + cycleLen2);
			}
			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 200000;
			int cycleLen1 = 66666, cycleLen2 = 66666, cycleLen3 = 66666;
			Edge[] edges = new Edge[n + 2];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			for (int j = 0; j < cycleLen2; j++) {
				edges[tmp++] = new Edge(j + cycleLen1, ((j + 1) % cycleLen2)
						+ cycleLen1);
			}
			for (int k = 0; k < cycleLen3; k++) {
				edges[tmp++] = new Edge(k + cycleLen1 + cycleLen2,
						((k + 1) % cycleLen3) + cycleLen1 + cycleLen2);
			}
			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
	}

	private void generateRest() {
		{
			int n = 12;
			int cycleLen1 = 4, cycleLen2 = 4, intersection = 2;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			int start = intersection - 1;
			int last = start;
			for (int i = 0; i < cycleLen2 - intersection; i++) {
				edges[tmp++] = new Edge(last, i + cycleLen1);
				last = i + cycleLen1;
			}
			edges[tmp++] = new Edge(last, 0);

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 300;
			int cycleLen1 = 150, cycleLen2 = 150, intersection = 120;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			int start = intersection - 1;
			int last = start;
			for (int i = 0; i < cycleLen2 - intersection; i++) {
				edges[tmp++] = new Edge(last, i + cycleLen1);
				last = i + cycleLen1;
			}
			edges[tmp++] = new Edge(last, 0);

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 9231;
			int cycleLen1 = 9000, cycleLen2 = 200, intersection = 2;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			int start = intersection - 1;
			int last = start;
			for (int i = 0; i < cycleLen2 - intersection; i++) {
				edges[tmp++] = new Edge(last, i + cycleLen1);
				last = i + cycleLen1;
			}
			edges[tmp++] = new Edge(last, 0);

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		{
			int n = 100000;
			int cycleLen1 = 23129, cycleLen2 = 39340, intersection = 21940;
			Edge[] edges = new Edge[n + 1];
			int tmp = 0;
			for (int i = 0; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
			}
			int start = intersection - 1;
			int last = start;
			for (int i = 0; i < cycleLen2 - intersection; i++) {
				edges[tmp++] = new Edge(last, i + cycleLen1);
				last = i + cycleLen1;
			}
			edges[tmp++] = new Edge(last, 0);

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}

		for (int IT = 0; IT < 3; IT++) { // THREE TESTS WITH VERTEX 0 ON ALL 3 CYCLES
			int n = 200000;
			int cycleLen1 = rng.nextInt(n / 4) + 3, 
					cycleLen2 = rng.nextInt(n / 4) + 3, 
					cycleLen3 = rng.nextInt(n / 4) + 3;
			
			Edge[] edges = new Edge[n + 2];
			int tmp = 0;
			
			int last = 0;
			for (int i = 1; i < cycleLen1; i++) {
				edges[tmp++] = new Edge(last, i);
				last = i;
			}
			edges[tmp++] = new Edge(last, 0);
			
			last = 0;
			for (int i = cycleLen1; i < cycleLen1 + cycleLen2 - 1; i++) {
				edges[tmp++] = new Edge(last, i);
				last = i;
			}
			edges[tmp++] = new Edge(last, 0);
			
			last = 0;
			for (int i = cycleLen1 + cycleLen2 - 1; i < cycleLen1 + cycleLen2 + cycleLen3 - 2; i++) {
				edges[tmp++] = new Edge(last, i);
				last = i;
			}
			edges[tmp++] = new Edge(last, 0);

			addUpAllEdges(edges, n, tmp);
			applyRandomPerm(n, edges);
			shuffleAll(edges);
			printTest(n, edges);
		}
		
		int n = 200000;
		int cycleLen1 = 199999, cycleLen2 = 199999, intersection = 199998;
		Edge[] edges = new Edge[n + 1];
		int tmp = 0;
		for (int i = 0; i < cycleLen1; i++) {
			edges[tmp++] = new Edge(i, (i + 1) % cycleLen1);
		}
		int start = intersection - 1;
		int last = start;
		for (int i = 0; i < cycleLen2 - intersection; i++) {
			edges[tmp++] = new Edge(last, i + cycleLen1);
			last = i + cycleLen1;
		}
		edges[tmp++] = new Edge(last, 0);
		
		addUpAllEdges(edges, n, tmp);
		applyRandomPerm(n, edges);
		shuffleAll(edges);
		printTest(n, edges);
	}

	void printTest(int size, Edge[] edges) {
		try {
			countTests++;
			String fileName = (isPreliminary) ? ("../preliminary/")
					: ("../tests/");
			fileName += String.format("%02d", countTests);
			out = new PrintWriter(fileName);

			out.println(size + " " + edges.length);
			for (Edge e : edges) {
				out.println(e);
			}

			System.out.println("Done printing test #" + countTests);
			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
}