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

public class SecureTestGen {

	final int MAX_N = 5_000;
	final int MAX_M = 100_000;
	final int MAX_COST = 100_000;
	final static Random rng = new Random("secure".hashCode());

	public static void main(String[] args) {
		new SecureTestGen().generate();
	}

	PrintWriter out;
	int countTests = 0;

	void generate() {
		createTestsDir();
		generateSamples();

		generateSmall();
		generateMedium();
		generateLarge();
	}

	private void generateSamples() {
		printSample1();
		printSample2();
	}

	void printSample1() {
		TestCase tc = new TestCase(6);
		tc.addBlack(0, 2);
		tc.addWhite(3, 4);

		tc.addEdge(0, 2, 3);
		tc.addEdge(0, 1, 4);
		tc.addEdge(1, 2, 3);
		tc.addEdge(1, 3, 2);
		tc.addEdge(0, 5, 5);
		tc.addEdge(2, 4, 6);
		tc.addEdge(4, 5, 1);

		printTest(tc);
	}

	void printSample2() {
		TestCase tc = new TestCase(4);
		tc.addBlack(0);
		tc.addWhite(3);

		tc.addEdge(0, 2, 3);
		tc.addEdge(1, 3, 2);

		printTest(tc);
	}

	private void generateSmall() {
		{ // 3
			TestCase tc = new TestCase(2);
			tc.addWhite(0);
			tc.addBlack(1);
			tc.addEdge(0, 1, 1);
			printTest(tc);
		}
		{ // 4
			TestCase tc = new TestCase(2);
			tc.addWhite(1);
			tc.addBlack(0);
			tc.addEdge(0, 1, MAX_COST);
			printTest(tc);
		}
		{ // 5
			TestCase tc = new TestCase(3);
			tc.addWhite(0);
			tc.addBlack(2);
			tc.addEdge(0, 2, 2);
			printTest(tc);
		}
		{ // 6
			TestCase tc = new TestCase(3);
			tc.addBlack(0);
			tc.addWhite(1);
			tc.addEdge(0, 2, 2);
			printTest(tc);
		}
		{ // 7
			TestCase tc = new TestCase(3);
			tc.addBlack(0);
			tc.addWhite(2);
			tc.addEdge(0, 1, 1);
			tc.addEdge(1, 2, 3);
			printTest(tc);
		}
		{ // 8
			TestCase tc = new TestCase(3);
			tc.addBlack(0);
			tc.addWhite(2);
			tc.addEdge(0, 1, 3);
			tc.addEdge(1, 2, 3);
			tc.addEdge(0, 2, 5);
			printTest(tc);
		}
		{ // 9
			TestCase tc = new TestCase(3);
			tc.addBlack(0, 1);
			tc.addWhite(2);
			tc.addEdge(0, 1, 1);
			tc.addEdge(1, 2, 3);
			tc.addEdge(0, 2, 2);
			printTest(tc);
		}
		{ // 10
			TestCase tc = new TestCase(3);
			tc.addBlack(0, 1);
			tc.addWhite(2);
			tc.addEdge(0, 1, 1);
			tc.addEdge(1, 2, 3);
			tc.addEdge(0, 2, 2);
			printTest(tc);
		}

		for (int test = 11; test <= 13; test++) {
			int n = 10;
			printRandomTree(n, (test - 9), (test - 9), 1, 100);
		}
		
		for (int test = 14; test <= 17; test++) {
			int n = 10;
			int black = 1, white = 1;
			printRandomGraph(n, 2 * (test - 13), black, white, 1, 100);
		}


		for (int test = 18; test <= 20; test++) {
			int n = 10;
			printComplete(n, (test - 16), (test - 16), 1, 100);
		}
	}

	private void generateMedium() {
		for (int test = 21; test <= 23; test++) {
			int n = 100;
			int black = randRange(1, n / 2), white = randRange(1, n / 2);
			printComplete(n, black, white, 1, 1000);
		}
		
		for (int test = 24; test <= 27; test++) {
			int n = 150;
			int black = n / 10, white = n / 10;
			printRandomGraph(n, 5 * (test - 23), black, white, 1, 1000);
		}

		for (int test = 28; test <= 30; test++) {
			int n = 200;
			printRandomTree(n, n / 6 * (test - 27), n / 6 * (test - 27), 1,
					1000);
		}
	}

	private void generateLarge() {
		for (int test = 31; test <= 35; test++) {
			int n = MAX_N;
			printRandomTree(n, MAX_N / 10 * (test - 30), MAX_N / 10
					* (test - 30), 1, MAX_COST);
		}

		for (int test = 36; test <= 40; test++) {
			int n = MAX_N / 5 * (test - 35);
			printRandomGraph(n, MAX_M, randRange(1, n / 2),
					randRange(1, n / 2), 1, MAX_COST);
		}

		// 41
		printAntiFordBellman(MAX_N);

		// 42
		printAntiFordBellmanInverse(MAX_N);

		// 43
		printManyBlackWhite(MAX_N);

		// 44
		printManyBlackWhiteNoPath(MAX_N);
		
		// 45
		printWhiteIsolated(MAX_N, MAX_N - 1, 1);

		// 46-50
		printRandomGraph(MAX_N, 100, 5, 5, 1, MAX_COST);

		printRandomGraph(MAX_N, MAX_M, 3, 3, MAX_COST / 2, MAX_COST);
		printRandomGraph(MAX_N, MAX_M, 50, 50, MAX_COST / 2, MAX_COST);

		printRandomGraph(MAX_N, MAX_M, 1, MAX_N - 1, 1, MAX_COST);
		printRandomGraph(MAX_N, MAX_M, MAX_N - 1, 1, 1, MAX_COST);
		
		// 51
		printAntiFordBellmanQueue(MAX_N);
	}
	
	

	private void printAntiFordBellmanQueue(int n) {
		TestCase tc = new TestCase(n);
		tc.addBlack(0);
		tc.addWhite(n - 1);
		
		for (int i = n - 1; i > 1; i--) {
			tc.addEdge(0, i, 3 * i + 1);
		}
		
		for (int i = 0; i < n - 1; i++) {
			tc.addEdge(i, i + 1, 1);
		}
		
		int rmnEdges = MAX_M - tc.edges.size();
		for (int i = 0; i < rmnEdges; i++) {
			int u = randRange(0, n - 1);
			int v = randRange(0, n - 1);
			while (!tc.addEdge(u, v, MAX_COST)) {
				u = randRange(0, n - 1);
				v = randRange(0, n - 1);
			}
		}

		printTest(tc);
	}

	private void printWhiteIsolated(int n, int black, int white) {
		TestCase tc = new TestCase(n);
		for (int i = 0; i < black; i++) {
			tc.addBlack(i);
		}
		for (int i = n - white; i < n; i++) {
			tc.addWhite(i);
		}
		for (int i = 0; i < MAX_M; i++) {
			int u = rng.nextInt(n - white), v = rng.nextInt(n - white);
			int cost = randRange(1, MAX_COST);
			while (!tc.addEdge(u, v, cost)) {
				u = rng.nextInt(n - white);
				v = rng.nextInt(n - white);
			}
		}
		printTest(tc);
	}

	private void printManyBlackWhiteNoPath(int n) {
		TestCase tc = new TestCase(n);
		for (int i = 0; i < n; i++) {
			if (i < n / 2) {
				tc.addBlack(i);
			} else {
				tc.addWhite(i);
			}
		}

		for (int i = 0; i < MAX_M / 2; i++) {
			int from = 0, to = n / 2 - 1;
			int u = randRange(from, to), v = randRange(from, to);
			while (!tc.addEdge(u, v, MAX_COST)) {
				u = randRange(from, to);
				v = randRange(from, to);
			}
		}

		for (int i = 0; i < MAX_M / 2; i++) {
			int from = n / 2, to = n - 1;
			int u = randRange(from, to), v = randRange(from, to);
			while (!tc.addEdge(u, v, MAX_COST)) {
				u = randRange(from, to);
				v = randRange(from, to);
			}
		}
		printTest(tc);
	}

	private void printManyBlackWhite(int n) {
		TestCase tc = new TestCase(n);

		int black = n / 4, white = n / 4;
		for (int i = 0; i < black; i++) {
			tc.addBlack(i);
			tc.addEdge(i, black, 1);
		}

		for (int i = n - white; i < n; i++) {
			tc.addWhite(i);
			tc.addEdge(n - white - 1, i, 1);
		}

		for (int i = black; i < n - white - 1; i++) {
			tc.addEdge(i, i + 1, 1);
		}

		int rmnEdges = MAX_M - tc.edges.size();
		for (int i = 0; i < rmnEdges; i++) {
			int u = randRange(black, n - white - 1);
			int v = randRange(black, n - white - 1);
			while (!tc.addEdge(u, v, MAX_COST)) {
				u = randRange(black, n - white - 1);
				v = randRange(black, n - white - 1);
			}
		}

		printTest(tc);
	}

	void printAntiFordBellman(int n) {
		TestCase tc = new TestCase(n);
		tc.addBlack(0);
		tc.addWhite(n - 1);

		int smallEdges = n - 1;
		int bigEdges = MAX_M - smallEdges;
		
		for (int i = 0; i < bigEdges; i++) {
			int u = rng.nextInt(n), v = rng.nextInt(n);
			while (!tc.addEdge(u, v, MAX_COST)) {
				u = rng.nextInt(n);
				v = rng.nextInt(n);
			}
		}
		
		for (int i = n - 1; i > 0; i--) {
			tc.addEdge(i, i - 1, 1);
		}

		printTest(tc);
	}

	void printAntiFordBellmanInverse(int n) {
		TestCase tc = new TestCase(n);
		tc.addWhite(0);
		tc.addBlack(n - 1);

		int smallEdges = n - 1;
		int bigEdges = MAX_M - smallEdges;

		for (int i = 0; i < bigEdges; i++) {
			int u = rng.nextInt(n), v = rng.nextInt(n);
			while (!tc.addEdge(u, v, MAX_COST)) {
				u = rng.nextInt(n);
				v = rng.nextInt(n);
			}
		}

		for (int i = n - 1; i > 0; i--) {
			tc.addEdge(i, i - 1, 1);
		}

		printTest(tc);
	}

	void printComplete(int n, int black, int white, int minCost, int maxCost) {
		TestCase tc = new TestCase(n);

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				tc.addEdge(i, j, randRange(minCost, maxCost));
			}
		}

		tc.setTypes(getTypes(n, black, white));
		printTest(tc);
	}

	void printRandomGraph(int n, int m, int black, int white, int minCost,
			int maxCost) {
		TestCase tc = new TestCase(n);

		for (int i = 0; i < m; i++) {
			int u = rng.nextInt(n), v = rng.nextInt(n);
			int cost = randRange(minCost, maxCost);
			while (!tc.addEdge(u, v, cost)) {
				u = rng.nextInt(n);
				v = rng.nextInt(n);
			}
		}

		tc.setTypes(getTypes(n, black, white));
		printTest(tc);
	}

	void printRandomTree(int n, int black, int white, int minCost, int maxCost) {
		TestCase tc = new TestCase(n);
		DSU dsu = new DSU(n);

		for (int i = 0; i < n - 1; i++) {
			int u = rng.nextInt(n), v = rng.nextInt(n);
			while (!dsu.union(u, v)) {
				u = rng.nextInt(n);
				v = rng.nextInt(n);
			}
			tc.addEdge(u, v, randRange(minCost, maxCost));
		}

		tc.setTypes(getTypes(n, black, white));
		printTest(tc);
	}

	int[] getTypes(int n, int black, int white) {
		int[] type = new int[n];
		for (int i = 0; i < black; i++) {
			int t = rng.nextInt(n);
			while (type[t] != 0) {
				t = rng.nextInt(n);
			}
			type[t] = 1;
		}
		for (int i = 0; i < white; i++) {
			int t = rng.nextInt(n);
			while (type[t] != 0) {
				t = rng.nextInt(n);
			}
			type[t] = 2;
		}
		return type;
	}

	int randRange(int from, int to) {
		return from + rng.nextInt(to - from + 1);
	}

	class DSU {
		int[] parent, rank;

		public DSU(int n) {
			parent = new int[n];
			rank = new int[n];
			for (int i = 0; i < n; i++) {
				parent[i] = i;
			}
		}

		int get(int v) {
			if (parent[v] == v) {
				return v;
			}
			return parent[v] = get(parent[v]);
		}

		boolean union(int a, int b) {
			a = get(a);
			b = get(b);
			if (a == b) {
				return false;
			}

			if (rank[a] == rank[b]) {
				rank[a]++;
			}
			if (rank[a] > rank[b]) {
				parent[b] = a;
			} else {
				parent[a] = b;
			}
			return true;
		}

	}

	class TestCase {
		int vertices;
		List<Integer> black, white;
		List<Edge> edges;
		Set<Integer> used;
		
		class Edge {
			int from, to, cost;

			public Edge(int from, int to, int cost) {
				this.from = from;
				this.to = to;
				this.cost = cost;
			}

			@Override
			public String toString() {
				return (from + 1) + " " + (to + 1) + " " + cost;
			}
		}

		public TestCase(int size) {
			this.vertices = size;
			black = new ArrayList<>();
			white = new ArrayList<>();
			edges = new ArrayList<>();
			used = new HashSet<>();
		}

		public boolean addEdge(int from, int to, int cost) {
			if (from == to) {
				return false;
			}
			int key = Math.min(from, to) * vertices + Math.max(from, to);
			if (used.contains(key)) {
				return false;
			}
			
			used.add(key);
			this.edges.add(new Edge(from, to, cost));
			return true;
		}

		public void addBlack(int... vs) {
			for (int v : vs) {
				this.black.add(v);
			}
		}

		public void addWhite(int... vs) {
			for (int v : vs) {
				this.white.add(v);
			}
		}

		public void setTypes(int[] types) {
			for (int i = 0; i < types.length; i++) {
				if (types[i] == 1) {
					black.add(i);
				} else if (types[i] == 2) {
					white.add(i);
				}
			}
		}

		public int[] getColors() {
			int[] color = new int[vertices];
			if (black.size() == 0 || white.size() == 0) {
				throw new AssertionError();
			}
			for (int i : black) {
				if (color[i] != 0) {
					throw new AssertionError();
				}
				color[i] = 1;
			}
			for (int j : white) {
				if (color[j] != 0) {
					throw new AssertionError();
				}
				color[j] = 2;
			}
			return color;
		}
	}

	void createTestsDir() {
		File file = new File("../tests/");
		if (!file.exists()) {
			file.mkdir();
		}
	}

	void printTest(TestCase tc) {
		try {
			countTests++;
			String fileName = "../tests/";
			fileName += String.format("%02d", countTests);
			out = new PrintWriter(fileName);

			out.println(tc.vertices + " " + tc.edges.size());
			int[] color = tc.getColors();
			printArray(color);
			for (TestCase.Edge e : tc.edges) {
				out.println(e);
			}

			System.out.println("Done printing test #" + countTests);
			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			out.print(arr[i]);
			if (i + 1 == arr.length) {
				out.println();
			} else {
				out.print(" ");
			}
		}
	}
}
