/* 
 * Problem  : 	EXAM
 * Contest  : 	UOI-2006 (Dnepropetrovsk)
 * Type     : 	Test Generation
 * Date     : 	March 28, 2006
 * Author   : 	Shamil Yagiyayev
 * Language :	C#
 * Compiler :	.NET 1.1
 * Algorithm:	Random generation
 */

using System;
using System.IO;

public class Pair
{
	public int x;
	public int y;
	Pair (int xx, int yy)
	{	
		x = xx;
		y = yy;
	}
}

class GenExamRandom
{
	static Random rand = new Random();

	static bool[,] A;
	static bool[] boy;
	static int[] boys;
	static int[] girls;

	static void GenGraph(int n, int m, int nBoys)
	{
		A = new bool[n+1, n+1];
		boy = new bool[n+1];

		boys = new int[nBoys];
		girls = new int[n - nBoys];

		for (int i=1; i<=nBoys; i++) boy[i] = true;

		for (int i=1; i<=n; i++) 
		{
			int j  = rand.Next(1, n);
			bool c = boy[i];
			boy[i] = boy[j];
			boy[j] = c;
		}

		int b = 0;
		int g = 0;
		for (int i=1; i<=n; i++) if (boy[i]) boys[b++] = i; else girls[g++] = i;

		int pairNum = nBoys*(n-nBoys);
		bool[] p = new bool[pairNum];

		for (int i=0; i<pairNum && i<m; i++) p[i] = true;
		for (int i=0; i<pairNum; i++) 
		{
			int j  = rand.Next(1, pairNum);
			bool c = p[i];
			p[i] = p[j];
			p[j] = c;
		}

		int pn = 0;
		for (int i=0; i<nBoys; i++)
			for (int j=0;j<n-nBoys; j++)
				if (p[pn++])
				{
					A[boys[i],girls[j]] = true;
					A[girls[j], boys[i]] = true;
				}
	}

	static void Main(string[] args)
	{
		if (args.Length != 5)
		{
			Console.WriteLine("gen.exe <number of tests> <size N> <N boys> <size M> <file mask>");
			Console.WriteLine("For example: gen.exe 10 20 10 15 exam.{0}.dat");
		}

		int tests = int.Parse(args[0]);
		int n = int.Parse(args[1]);
		int nBoys = int.Parse(args[2]);
		int m = int.Parse(args[3]);
		string mask = args[4];

		for (int test=1; test<=tests; test++)
		{
			GenGraph(n, m, nBoys);
			StreamWriter sw = File.CreateText(String.Format(mask, test));
			sw.WriteLine("{0} {1}", n, m);
			for (int i=1; i<=n; i++)
				if (boy[i])
				for (int j=1; j<=n; j++)
					if (A[i,j])
					{
						sw.WriteLine("{0} {1}", i, j);
					}
		
			sw.Close();
		}
	}
}