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

public class TestsGen {
	static int testcount = 0;

	static Random random = new Random(4985739);
	
	static int MAXN = 16;
	static int MAXT = 1000;
	static int MAXP = 1000;

	static void write(int m, int[] t, int[] p, int[][] tab) throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		System.out.println("Generating test #" + testcount);
		out.println(t.length + " " + m);
		for (int i = 0; i < t.length; i++) {
			out.print(t[i] + " " + p[i] + " " + tab[i].length);
			for (int j : tab[i]) {
				out.print(" " + j);
			}
			out.println();
		}
		out.close();
	}

	static void writeRand(int n, int m, int maxt) throws IOException {
		int[] t = new int[n];
		int[] p = new int[n];
		int[][] tab = new int[n][];
		for (int i = 0; i < n; i++) {
			t[i]  = random.nextInt(maxt) + 1;
			p[i]  = random.nextInt(MAXP) + 1;
			tab[i] = new int[random.nextInt(n)];
			for (int j = 0; j < tab[i].length; j++) {
				out:while (true) {
					int cand = random.nextInt(n) + 1;
					if (cand == i + 1) continue;
					for (int k = 0; k < j; k++) {
						if (tab[i][k] == cand) continue out;
					}
					tab[i][j] = cand;
					break;
				}
			}
		}
		write(m, t, p, tab);
	}
	
	static void writeGoodRand(int n, int m, int maxt, int edges) throws IOException {
		int[] t = new int[n];
		int[] p = new int[n];
		int[][] tab = genGraph(n, edges);
		for (int i = 0; i < n; i++) {
			t[i]  = random.nextInt(maxt) + 1;
			p[i]  = random.nextInt(MAXP) + 1;
		}
		write(m, t, p, tab);
	}
	
	static int[][] genGraph(int n, int m) {
		ArrayList<Integer> num = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			num.add(i);
		}
		Collections.shuffle(num, random);
		boolean[][] tab = new boolean[n][n];
		for (int i = 0; i < m; i++) {
			while (true) {
				int a = random.nextInt(n);
				int b = random.nextInt(n);
				if (a == b || tab[a][b]) continue;
				tab[a][b] = tab[b][a] = true;
				break;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (tab[i][j]) {
					if (num.get(i) < num.get(j)) {
						tab[i][j] = false;
 					} else {
 						tab[j][i] = false;
 					}
				}
			}
		}
		int[][] ret = new int[n][];
		for (int i = 0; i < n; i++) {
			ArrayList<Integer> al = new ArrayList<Integer>();
			for (int j = 0; j < n; j++) {
				if (tab[i][j]) {
					al.add(j);
				}
			}
			ret[i] = new int[al.size()];
			for (int j = 0; j < al.size(); j++) {
				ret[i][j] = al.get(j) + 1;
			}
		}
		return ret;
	}
	
	static void writeAll(int n) throws IOException {
		int t = random.nextInt(MAXT);
		while (t < 2 * n) {
			t = random.nextInt(MAXT);
		}
		writeGoodRand(n, t, t / n, n * (n - 1) / 2);
	}
	
	static void writeGoodRandAll(int n, int maxt, int edges) throws IOException {
		int[] t = new int[n];
		int[] p = new int[n];
		int[][] tab = genGraph(n, edges);
		int m = 0;
		for (int i = 0; i < n; i++) {
			t[i]  = random.nextInt(maxt / n) + 1;
			m += t[i];
			p[i]  = random.nextInt(MAXP) + 1;
		}
		write(m, t, p, tab);
	}
	
	static void writeGoodRandAlmostAll(int n, int maxt, int edges) throws IOException {
		int[] t = new int[n];
		int[] p = new int[n];
		int[][] tab = genGraph(n, edges);
		int m = 0;
		for (int i = 0; i < n; i++) {
			t[i]  = random.nextInt(maxt / n) + 1;
			m += t[i];
			p[i]  = random.nextInt(MAXP) + 1;
		}
		write(m - 1, t, p, tab);
	}
	
	

	public static void main(String[] args) throws IOException {
		while (new File(String.format("%02d.t", testcount + 1)).exists()) {
			testcount++;
		}
		for (int i = 1; i <= MAXN; i++) {
			writeRand(i, MAXT, Math.min(2 * MAXT / i, MAXT));
			writeGoodRand(i, MAXT, Math.min(2 * MAXT / i, MAXT), 0);
			writeGoodRand(i, MAXT, Math.min(2 * MAXT / i, MAXT), Math.min(i, i * (i - 1) / 2));
			writeGoodRand(i, MAXT, Math.min(2 * MAXT / i, MAXT), i * (i - 1) / 2);
		}
		writeAll(2);
		writeAll(10);
		writeAll(MAXN);
		writeGoodRandAll(3, MAXT, 3 * 2 / 2);
		writeGoodRandAll(11, MAXT, 11 * 10 / 2);
		writeGoodRandAll(MAXN, MAXT, MAXN * (MAXN - 1) / 2);
		writeGoodRandAlmostAll(4, MAXT, 4 * 3 / 2);
		writeGoodRandAlmostAll(9, MAXT, 9 * 8 / 2);
		writeGoodRandAlmostAll(MAXN, MAXT, MAXN * (MAXN - 1) / 2);
	}

}
  