package tests;
//by Sergey Melnikov

import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;

public class TestGen extends Thread {
	class Test {
		int n, m;
		int[] t;
		int[][] a;

		public Test(int[] t, int[][] a) {
			this.n = t.length;
			this.m = a.length;
			this.t = t;
			this.a = a;
		}

	}

	private int testCount = 0;

	private void write(Test t) {
		try {
			++testCount;
			String filename = testCount / 10 + "" + testCount % 10;
			PrintWriter out = new PrintWriter(filename);
			System.err.println(testCount);
			out.println(t.n + " " + t.m);
			for (int i = 0; i < t.n; i++) {
				out.print(t.t[i] + (i == t.n - 1 ? "" : " "));
			}
			out.println();
			for (int i = 0; i < t.m; i++) {
				out.println(t.a[i][0] + " " + t.a[i][1]);
			}
			out.flush();
			out.close();
		} catch (IOException ex) {
			throw new RuntimeException(ex);
		}
	}

	void myAssert(boolean b) {
		if (!b)
			throw new AssertionError();
	}

	static Random rand = new Random(1);
	final int MAXN = 100;
	final int MAXM = 1000;
	final int MAXT = 1000;
	final Test[] example = { new Test(new int[] { 1, 2, 3, 4, 5 }, new int[][] {
			{ 1, 2 }, { 5, 3 }, { 1, 3 }, { 3, 4 }, { 2, 4 } }) };

	public void run() {
		for (int i = 0; i < example.length; i++) {
			write(example[i]);
		}
		write(genWithoutPrec(new int[] { 1 }));
		write(genWithoutPrec(new int[] { MAXN }));
		write(genWithoutPrec(randomArray(MAXN, 2)));
		write(genWithoutPrec(randomArray(MAXN, MAXT)));
		write(genWithoutPrec(randomArray(MAXN, MAXT, 0)));
		write(genWithoutPrec(randomArray(MAXN, MAXT, MAXN - 1)));
		write(genWithPrec(randomArray(10, 100), genPath(10)));
		write(genWithPrec(randomArray(MAXN, MAXT), genPath(MAXN)));
		write(genWithPrec(randomArray(MAXN, MAXT), genInHedgehog(MAXN)));
		write(genWithPrec(randomArray(MAXN, MAXT), genOutHedgehog(MAXN)));
		write(genWithPrec(randomArray(31, MAXT), genClique(31)));
		for (int n = 1; n <= MAXN; n *= 2) {
			for (int m = 1; m <= MAXM; m *= 2) {
				if (m > n * (n - 1) / 2)
					continue;
				write(genWithPrec(randomArray(n, MAXT), randomPrec(n, m)));
			}
		}
		for (int i = 0; i < 3; i++) {
			write(genWithPrec(randomArray(5, 10), randomPrec(5, 8)));
		}
		write(genWithPrec(randomArray(MAXN, MAXT), randomPrec(MAXN, MAXM)));

	}

	int[][] randomPrec(int n, int m) {
		int[][] res = new int[m][2];
		int[] p = genPermutation(n);
		boolean[][] a = new boolean[n][n];
		for (int it = 0; it < m; it++) {
			while (true) {
				int i = rand.nextInt(n);
				int j = rand.nextInt(n);
				if (p[i] >= p[j] || a[i][j])
					continue;
				res[it][0] = i + 1;
				res[it][1] = j + 1;
				a[i][j] = true;
				break;
			}
		}
		return res;
	}

	void floyd(boolean[][] b) {
		for (int k = 0; k < b.length; k++) {
			for (int i = 0; i < b.length; i++) {
				for (int j = 0; j < b.length; j++) {
					b[i][j] |= b[i][k] && b[k][i];
				}
			}
		}
	}

	int[][] genPath(int n) {
		int[][] res = new int[n - 1][2];
		int[] perm = genPermutation(n);
		for (int i = 0; i < res.length; i++) {
			res[i][0] = perm[i] + 1;
			res[i][1] = perm[i + 1] + 1;
		}
		shuffle(res);
		return res;
	}

	int[][] genInHedgehog(int n) {
		int[][] res = new int[n - 1][2];
		int[] perm = genPermutation(n);
		for (int i = 0; i < res.length; i++) {
			res[i][0] = perm[i] + 1;
			res[i][1] = perm[n - 1] + 1;
		}
		shuffle(res);
		return res;
	}

	int[][] genOutHedgehog(int n) {
		int[][] res = new int[n - 1][2];
		int[] perm = genPermutation(n);
		for (int i = 0; i < res.length; i++) {
			res[i][0] = perm[n - 1] + 1;
			res[i][1] = perm[i] + 1;
		}
		shuffle(res);
		return res;
	}

	int[][] genClique(int n) {
		int[][] res = new int[n * (n - 1) / 2][2];
		int[] perm = genPermutation(n);
		int it = 0;
		for (int i = 0; i < perm.length; i++) {
			for (int j = 0; j < perm.length; j++) {
				if (i != j && perm[i] < perm[j]) {
					res[it][0] = i + 1;
					res[it][1] = j + 1;
					it++;
				}
			}
		}
		assert it == res.length;
		shuffle(res);
		return res;
	}

	int[] genPermutation(int n) {
		int[] a = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = i;
		}
		shuffle(a);
		return a;
	}

	void shuffle(Object[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int x = rand.nextInt(i + 1);
			Object p = arr[x];
			arr[x] = arr[i];
			arr[i] = p;
		}
	}

	void shuffle(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int x = rand.nextInt(i + 1);
			int p = arr[x];
			arr[x] = arr[i];
			arr[i] = p;
		}
	}

	int[] randomArray(int n, int max) {
		int[] res = new int[n];
		for (int i = 0; i < res.length; i++) {
			res[i] = rand.nextInt(max) + 1;
		}
		return res;
	}

	int[] randomArray(int n, int max, int maxpos) {
		int[] res = new int[n];
		int j = -1;
		for (int i = 0; i < res.length; i++) {
			res[i] = rand.nextInt(max) + 1;
			if (j == -1 || res[i] > res[j]) {
				j = i;
			}
		}
		int tmp = res[maxpos];
		res[maxpos] = res[j];
		res[j] = tmp;
		return res;
	}

	Test genWithoutPrec(int[] t) {
		return new Test(t, new int[][] {});
	}

	Test genWithPrec(int[] t, int[][] prec) {
		return new Test(t, prec);
	}

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