import java.io.*;
import java.security.acl.Owner;
import java.util.*;

// Version 1.0 Stable

public class TestsGen {

	static class Graph {
		int n;
		ArrayList<Integer>[] edge;
		int onepow;

		public Graph(int n, int onepow) {
			this.n = n;
			this.onepow = onepow;
			edge = new ArrayList[n];
			for (int i = 0; i < n; i++) {
				edge[i] = new ArrayList<Integer>();
			}
			for (int i = n - onepow; i < n; i++) {
				int v = rand.nextInt(n - onepow);
				addEdge(v, i);
			}
		}

		public boolean check() {
			boolean[] used;
			class DFSActor {
				final public boolean[] used;

				public DFSActor(int n) {
					used = new boolean[n];
					dfs(0);
				}

				private void dfs(int u) {
					if (used[u]) {
						return;
					}
					used[u] = true;
					for (int v : edge[u]) {
						dfs(v);
					}
				}
			}
			used = new DFSActor(n).used;
			for (int i = 0; i < n; i++) {
				if (!used[i]) {
					return false;
				}
			}
			return true;
		}

		public void addEdge(int v1, int v2) {
			edge[v1].add(v2);
			edge[v2].add(v1);
		}

		public void makeNormal() {
			for (int i = 0; i < n - onepow; i++) {
				while (edge[i].size() < 2) {
					int x = rand.nextInt(n - onepow);
					while (x == i) {
						x = rand.nextInt(n - onepow);
					}
					addEdge(x, i);
				}
			}
		}

		public void addRandomEdges(int k) {
			for (int i = 0; i < k; i++) {
				int st1 = rand.nextInt(n - onepow);
				int st2 = rand.nextInt(n - onepow);
				while (st1 == st2) {
					st1 = rand.nextInt(n - onepow);
					st2 = rand.nextInt(n - onepow);
				}
				addEdge(st1, st2);
			}
		}

		public void addCycle(int k) {
			ArrayList<Integer> incycle = new ArrayList<Integer>();
			for (int i = 0; i < n - onepow; i++) {
				incycle.add(i);
			}
			Collections.shuffle(incycle, rand);
			int t = rand.nextInt(3) + 2;
			int[] prev = new int[t];
			Arrays.fill(prev, incycle.get(0));
			for (int i = 1; i < k - 1; i++) {
				int curv = incycle.get(i);
				int par = rand.nextInt(t);
				addEdge(curv, prev[par]);
				prev[par] = curv;
			}
			int curv = incycle.get(k - 1);
			for (int i = 0; i < t; i++) {
				addEdge(curv, prev[i]);
			}

		}

		public void print(PrintWriter out) {
			ArrayList<Integer> left = new ArrayList<Integer>();
			ArrayList<Integer> right = new ArrayList<Integer>();

			ArrayList<Integer> numv = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				numv.add(i + 1);
			}
			Collections.shuffle(numv, rand);

			for (int i = 0; i < n; i++) {
				for (int j : edge[i]) {
					if (i < j && rand.nextBoolean()) {
						left.add(numv.get(i));
						right.add(numv.get(j));
					} else if (i < j) {
						left.add(numv.get(j));
						right.add(numv.get(i));
					}
				}
			}

			ArrayList<Integer> nume = new ArrayList<>();
			for (int i = 0; i < left.size(); i++) {
				nume.add(i);
			}
			Collections.shuffle(nume, rand);
			out.println(n + " " + left.size());
			for (int i = 0; i < left.size(); i++) {
				out.println(left.get(nume.get(i)) + " "
						+ right.get(nume.get(i)));
			}
		}
	}

	static int done = 0;

	static final Random rand = new Random(556668949239L);
	static ArrayList<Integer> data = new ArrayList<Integer>();

	static String str = "../tests/";

	static void print(Graph g) throws IOException {
		done++;
		System.err.println(done);
		PrintWriter out;
		if (done < 10)
			out = new PrintWriter(str + "0" + String.valueOf(done));
		else
			out = new PrintWriter(str + String.valueOf(done));
		System.err.println(g.check());
		g.print(out);
		out.close();
	}

	static void genSimple() throws IOException {
		PrintWriter out;
		out = new PrintWriter("../preliminary/01");
		out.println("5 6");
		out.println("1 2");
		out.println("2 3");
		out.println("1 3");
		out.println("1 4");
		out.println("4 5");
		out.println("1 5");
		out.close();
	}

	static void genTest(int n, int v) throws IOException {
		Graph g = new Graph(n + rand.nextInt(n / 2), v);
		g.makeNormal();
		print(g);
	}

	static void genSmartTest(int n, int v) throws IOException {
		System.err.println(v);
		Graph g = new Graph(n, v);
		g.addRandomEdges(n / 2 + rand.nextInt(2));
		int k = 1 + rand.nextInt(3);
		for (int i = 0; i < k; i++) {
			g.addCycle(n / 3 + rand.nextInt(n / 2));
		}
		g.makeNormal();
		print(g);
	}

	public static void main(String[] args) throws IOException {
		// boolean f = (new File("../preliminary")).mkdir();
		//boolean f = new File("../tests").mkdir();
		genSimple();
		genTest(4, 0);
		genTest(4, 0);
		genTest(4, 1);
		genTest(4, 2);
		genTest(1000, rand.nextInt(10) + 2);
		for (int i = 0; i < 7; i++) {
			genSmartTest(500 + rand.nextInt(300), rand.nextInt(2));
		}
		genTest(30000, rand.nextInt(10) + 2);
		for (int i = 0; i < 7; i++) {
			rand.nextInt();
			genSmartTest(30000 + rand.nextInt(20000), rand.nextInt(2));
		}
		done = 0;

		return;
	}
}
