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

public class TestGen {
	public static void main(String[] args) {
		new TestGen().run();
	}

	BufferedReader br;
	StringTokenizer in;
	PrintWriter out;

	public String nextToken() throws IOException {
		while (in == null || !in.hasMoreTokens()) {
			in = new StringTokenizer(br.readLine());
		}
		return in.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	Random rnd;
	int tNumber;

	class Edge {
		int a, b;

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + a;
			result = prime * result + b;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Edge other = (Edge) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (a != other.a)
				return false;
			if (b != other.b)
				return false;
			return true;
		}

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

		private TestGen getOuterType() {
			return TestGen.this;
		}
	}

	class Test {
		int n, m, k;
		ArrayList<Edge> e;

		public void shuffle() {
			ArrayList<Integer> a = new ArrayList<Integer>();
			for (int i = 0; i < n; i++) {
				a.add(i);
			}
			Collections.shuffle(a, rnd);
			for (int i = 0; i < m; i++) {
				e.set(i, new Edge(a.get(e.get(i).a), a.get(e.get(i).b)));
			}
			for (int i = 0; i < m; i++) {
				if (rnd.nextBoolean()) {
					e.set(i, new Edge(e.get(i).b, e.get(i).a));
				}
			}
			Collections.shuffle(e, rnd);
		}

		public void printTest() throws IOException {
			if (tNumber < 10)
				out = new PrintWriter("0" + tNumber);
			else
				out = new PrintWriter("" + tNumber);
			tNumber++;
			shuffle();
			out.println(n + " " + m);
			for (int i = 0; i < m; i++)
				out.println((e.get(i).a + 1) + " " + (e.get(i).b + 1));
			out.close();
		}

		public void generate(int N, int K, int M, int km) {
			n = N;
			m = M;
			k = K;
			e = new ArrayList<Edge>();
			HashSet<Edge> was = new HashSet<Edge>();
			for (int i = 1; i < k; i++) {
				int a = rnd.nextInt(i);
				was.add(new Edge(a, i));
				was.add(new Edge(i, a));
				e.add(new Edge(i, a));
			}
			for (int i = 0; i < km - k + 1; i++) {
				int a = rnd.nextInt(k - 1) + 1;
				int b = rnd.nextInt(a);
				if (!was.contains(new Edge(a, b))) {
					e.add(new Edge(a, b));
					was.add(new Edge(a, b));
					was.add(new Edge(b, a));
				}
				else
					i--;
			}
		}
		
		public void addChain(int t) {
			if (k == n)
				return;
			if (k + t > n)
				t = n - k;
			if (t <= 0)
				return;
			e.add(new Edge(rnd.nextInt(k), k));
			for (int i = k + 1; i < k + t; i++) {
				e.add(new Edge(i - 1 , i));
			}
			k += t;
		}
		
		public void addChainToRoot (int t) {
			if (k == n)
				return;
			if (k + t > n)
				t = n - k;
			if (t <= 0)
				return;
			e.add(new Edge(0, k));
			for (int i = k + 1; i < k + t; i++) {
				e.add(new Edge(i - 1 , i));
			}
			k += t;
		}
	}

	public void solve() throws IOException {
		tNumber = 1;
		rnd = new Random(31);
		Test t = new Test();
		
		t.generate(25, 1, 24, 0);
		for (int i = 0; i < 5; i++) {
			t.addChainToRoot(5 + rnd.nextInt(4));
		}
		t.printTest();
		
		t.generate(100, 1, 99, 0);
		for (int i = 0; i < 10; i++) {
			t.addChainToRoot(10 + rnd.nextInt(20));
		}
		t.printTest();
		
		t.generate(100, 1, 99, 0);
		t.addChainToRoot(99);
		t.printTest();
		
		t.generate(100, 1, 99, 0);
		t.addChainToRoot(35);
		t.addChain(64);
		t.printTest();
		
		t.generate(100, 1, 99, 0);
		t.addChainToRoot(99);
		t.m++;
		t.e.add(new Edge(0, 99));
		t.printTest();
		
		t.generate(100, 100, 1000, 1000);
		t.printTest();
		
		t.generate(50, 1, 49, 0);
		for (int i = 0; i < 10; i++) {
			t.addChain(5 + rnd.nextInt(10));
		}
		t.printTest();
		
		t.generate(100, 1, 99, 0);
		for (int i = 0; i < 10; i++) {
			t.addChain(10 + rnd.nextInt(20));
		}
		t.printTest();
		
		t.generate(50, 20, 80, 50);
		for (int i = 0; i < 6; i++) {
			t.addChain(5 + rnd.nextInt(5));
		}
		t.printTest();
		
		t.generate(100, 40, 140, 80);
		for (int i = 0; i < 10; i++) {
			t.addChain(10 + rnd.nextInt(20));
		}
		t.printTest();
		
		
		t.generate(25000, 1, 24999, 0);
		for (int i = 0; i < 5; i++) {
			t.addChainToRoot(5000 + rnd.nextInt(4000));
		}
		t.printTest();
		
		t.generate(100000, 1, 99999, 0);
		for (int i = 0; i < 10; i++) {
			t.addChainToRoot(10000 + rnd.nextInt(20000));
		}
		t.printTest();
		
		t.generate(100000, 1, 99999, 0);
		t.addChainToRoot(99999);
		t.printTest();
		
		t.generate(100000, 1, 99999, 0);
		t.addChainToRoot(35999);
		t.addChain(64999);
		t.printTest();
		
		t.generate(100000, 1, 99999, 0);
		t.addChainToRoot(99999);
		t.m++;
		t.e.add(new Edge(0, 99999));
		t.printTest();
		
		t.generate(100000, 100000, 200000, 200000);
		t.printTest();
		
		t.generate(50000, 1, 49999, 0);
		for (int i = 0; i < 10; i++) {
			t.addChain(5000 + rnd.nextInt(10000));
		}
		t.printTest();
		
		t.generate(100000, 1, 99999, 0);
		for (int i = 0; i < 10; i++) {
			t.addChain(10000 + rnd.nextInt(20000));
		}
		t.printTest();
		
		t.generate(50000, 20000, 80000, 50000);
		for (int i = 0; i < 6; i++) {
			t.addChain(5000 + rnd.nextInt(5000));
		}
		t.printTest();
		
		t.generate(100000, 40000, 140000, 80000);
		for (int i = 0; i < 10; i++) {
			t.addChain(10000 + rnd.nextInt(20000));
		}
		t.printTest();

		for (int i = 0; i < 5; i++) {
			int n = rnd.nextInt(50000) + 50000;
			int k = n / 5;
			int m = n - k + 20000 + rnd.nextInt(20000);
			t.generate(n, k, m, m - (n - k));
			for (int j = 0; j < 20; j++) {
				t.addChain(rnd.nextInt(10000) + 10000);
			}
			t.printTest();
		}
		
	}

	public void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			solve();

		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
}