import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class TestGen extends Thread {

	class Edge {
		int from, to;
		String w;

		public Edge(int from, int to, String w) {
			this.from = from + 1;
			this.to = to + 1;
			assert 1 <= w.length() && w.length() <= 10;
			this.w = w;
		}

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

	}

	class Test {
		int n, s, t;
		ArrayList<Edge> e;

		public Test(int n, int s, int t, Edge... e) {
			this.n = n;
			this.s = s + 1;
			this.t = t + 1;
			this.e = new ArrayList<Edge>(Arrays.asList(e));
		}

		public Test(int n, int s, int t, ArrayList<Edge> e) {
			this.n = n;
			this.s = s + 1;
			this.t = t + 1;
			this.e = e;
		}

	}

	private int testCount = 10;

	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.e.size());
			for (Edge e : t.e) {
				out.println(e);
			}
			assert t.s != t.t;
			out.println(t.s + " " + t.t);
			out.println();
			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);

	String randString(int len, int alphabet) {
		String s = "";
		for (int i = 0; i < len; i++) {
			s += (char) ('a' + rand.nextInt(alphabet));
		}
		// System.err.println(s);
		return s;
	}

	Test genRandTest(int n, int m) {
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < m; i++) {
			int a = rand.nextInt(n);
			int b;
			do {
				b = rand.nextInt(n);
			} while (a == b);
			e.add(new Edge(a, b, randString(10, 26)));
		}
		int s = rand.nextInt(n);
		int t;
		do {
			t = rand.nextInt(n);
		} while (s == t);
		Collections.shuffle(e, rand);
		return new Test(n, s, t, e);
	}

	Test genRandAntiGreedTest(int n, int m, int pr) {
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < m;) {
			int a = rand.nextInt(n);
			int b;
			do {
				b = rand.nextInt(n);
			} while (a == b);
			String s = randString(rand.nextInt(10) + 1, 26);
			// System.err.println(s);
			e.add(new Edge(a, b, s));
			i++;
			if (i + 1 < m && rand.nextInt(pr) == 0 && s.length() > 1) {
				e.add(new Edge(a, b, s.substring(0,
						rand.nextInt(s.length()) + 1)));
				i++;
			}
		}
		int s = rand.nextInt(n);
		int t;
		do {
			t = rand.nextInt(n);
		} while (s == t);
		Collections.shuffle(e, rand);
		return new Test(n, s, t, e);
	}

	int[] genPerm(int n) {
		int[] p = new int[n];
		for (int i = 0; i < p.length; i++) {
			int x = rand.nextInt(i + 1);
			p[i] = p[x];
			p[x] = i;
		}
		return p;
	}

	Test genConstFir(int n, int m, int len) {
		int[] p = genPerm(n);
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < p.length - 1; i++) {
			e.add(new Edge(p[i], p[i + 1], randString(len, 26)));
		}
		while (e.size() < m) {
			int b = rand.nextInt(p.length - 2) + 1;
			int a = rand.nextInt(b);
			e.add(new Edge(p[b], p[a], randString(rand.nextInt(10) + 1, 26)));
		}
		Collections.shuffle(e, rand);
		return new Test(n, p[0], p[n - 1], e);
	}

	Test genRandFir(int n, int m) {
		int[] p = genPerm(n);
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < p.length - 1; i++) {
			e
					.add(new Edge(p[i], p[i + 1], randString(
							rand.nextInt(10) + 1, 26)));
		}
		while (e.size() < m) {
			int b = rand.nextInt(p.length - 2) + 1;
			int a = rand.nextInt(b);
			e.add(new Edge(p[b], p[a], randString(rand.nextInt(10) + 1, 26)));
		}
		Collections.shuffle(e, rand);
		return new Test(n, p[0], p[n - 1], e);
	}

	Test genRandMultiFir(int n, int m, int k) {
		int[] p = genPerm(n);
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < p.length - 1; i++) {
			e
					.add(new Edge(p[i], p[i + 1], randString(
							rand.nextInt(10) + 1, 26)));
		}
		while (e.size() < m) {
			int a, b;
			do {
				a = rand.nextInt(p.length);
				b = rand.nextInt(p.length);
			} while (a == b || b > a + k);
			e.add(new Edge(p[a], p[b], randString(rand.nextInt(10) + 1, 26)));
		}
		Collections.shuffle(e, rand);
		return new Test(n, p[0], p[n - 1], e);
	}

	Test genRandStick(int n) {
		int[] p = genPerm(n);
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < p.length - 1; i++) {
			e
					.add(new Edge(p[i], p[i + 1], randString(
							rand.nextInt(10) + 1, 26)));
		}
		Collections.shuffle(e, rand);
		return new Test(n, p[0], p[n - 1], e);
	}

	Test genRandAntiGreedMultiFir(int n, int m, int k) {
		int[] p = genPerm(n);
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < p.length - 1; i++) {
			e
					.add(new Edge(p[i], p[i + 1], randString(
							rand.nextInt(10) + 1, 26)));
		}
		while (e.size() < m) {
			int a, b;
			do {
				a = rand.nextInt(p.length);
				b = rand.nextInt(p.length);
			} while (a == b || b > a + k);
			if (b < a) {
				e
						.add(new Edge(p[a], p[b], randString(
								rand.nextInt(10) + 1, 26)));
			} else {
				int x = a;
				String s = "";
				while (s.length() <= 10 && x < b) {
					s += e.get(x).w;
					x++;
				}
				e.add(new Edge(p[a], p[b], s.substring(0, rand.nextInt(Math
						.min(s.length(), 10)) + 1)));
			}
		}
		Collections.shuffle(e, rand);
		return new Test(n, p[0], p[n - 1], e);
	}

	Test genMax1(boolean randomModify) {
		ArrayList<Edge> e = new ArrayList<Edge>();
		Integer[] ri = new Integer[2000];
		for (int i = 0; i < ri.length; ++i) {
			ri[i] = i;
		}
		Collections.shuffle(Arrays.asList(ri), rand);
		StringBuilder all = new StringBuilder();
		for (int i = 1; i < 2000; ++i) {
			all.append((char) ('a' + rand.nextInt(26)));
		}
		for (int i = 0; i < 1999; ++i) {
			e.add(new Edge(ri[i], ri[i + 1], "" + all.charAt(i)));
		}
		for (int j = 2000; j <= 50000; ++j) {
			int from = rand.nextInt(1999) + 1;
			int to = Math.min(2000, from + rand.nextInt(10) + 1);
			String s = "";
			for (int t = from; t < to; ++t) {
				char c = all.charAt(t - 1);
				if (randomModify && rand.nextInt(100) == 0) {
					c = (char) ('a' + rand.nextInt(26));
				}
				s += c;
			}
			e.add(new Edge(ri[from - 1], ri[to - 1], s));
		}
		Collections.shuffle(e, rand);
		return new Test(2000, ri[0], ri[1999], e);
	}

	Test genMax2(boolean randomModify, boolean lastIsAll) {
		ArrayList<Edge> e = new ArrayList<Edge>();
		Integer[] ri = new Integer[2000];
		for (int i = 0; i < ri.length; ++i) {
			ri[i] = i;
		}
		Collections.shuffle(Arrays.asList(ri), rand);
		String[] x = new String[1999];
		for (int i = 0; i < 1999; ++i) {
			StringBuilder v = new StringBuilder();
			for (int j = 0; j < 10; ++j) {
				v.append((char) ('a' + rand.nextInt(26)));
			}

			e.add(new Edge(ri[i], ri[i + 1], v.toString()));
			x[i] = v.toString();
		}
		for (int j = 2000; j <= 50000; ++j) {
			int from = lastIsAll ? 1999 : rand.nextInt(1999) + 1;
			String s = "";
			for (int t = 0; t < 10; ++t) {
				char c = x[from - 1].charAt(t);
				if (randomModify && rand.nextInt(100) == 0) {
					c = (char) ('a' + rand.nextInt(26));
				}
				s += c;
			}
			e.add(new Edge(ri[from - 1], ri[from], s));
		}
		Collections.shuffle(e, rand);
		return new Test(2000, ri[0], ri[1999], e);
	}

	Test genRandImpossibleSimple(int n, int m) {
		int[] p = genPerm(n);
		int k = rand.nextInt(n - 2) + 1;
		Set<Integer> A = new TreeSet<Integer>();
		Set<Integer> B = new TreeSet<Integer>();
		for (int i = 0; i < k; i++) {
			A.add(p[i]);
		}
		for (int i = k; i < p.length; i++) {
			B.add(p[i]);
		}
		ArrayList<Edge> e = new ArrayList<Edge>();
		for (int i = 0; i < m; i++) {
			int a, b;
			do {
				a = rand.nextInt(n);
				b = rand.nextInt(n);
			} while (a == b && (!A.contains(a) || !B.contains(b)));
			e.add(new Edge(a, b, randString(10, 26)));
		}
		int s = p[rand.nextInt(k)];
		int t = p[rand.nextInt(p.length - k) + k];
		Collections.shuffle(e, rand);
		return new Test(n, s, t, e);
	}

	public void run() {

		int n = 5;
		int m = 12;
		write(genRandMultiFir(5, 10, 2));
		write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandImpossibleSimple(n, m));
		n = 10;
		m = 50;
		write(genRandTest(n, m));
		write(genRandAntiGreedTest(n, m, 10));
		write(genRandMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandImpossibleSimple(n, m));
		n = 100;
		m = 5000;
		write(genRandAntiGreedTest(n, m, 10));
		write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandStick(n));
		n = 500;
		m = 50000;
		write(genRandAntiGreedTest(n, m, 10));
		write(genConstFir(n, m, 10));
		write(genRandMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandAntiGreedMultiFir(n, m, 3));
		write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandStick(n));
		write(genRandImpossibleSimple(n, m));
		n = 1000;
		m = 50000;
		write(genRandAntiGreedTest(n, m, 10));
		write(genConstFir(n, m, 10));
		write(genRandFir(n, m));
		write(genRandMultiFir(n, m, 3));
		write(genRandMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandAntiGreedMultiFir(n, m, 3));
		write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandStick(n));
		write(genRandImpossibleSimple(n, m));
		n = 2000;
		m = 50000;
		write(genRandMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandAntiGreedMultiFir(n, m, 3));
		write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		write(genRandStick(n));		
		write(genMax2(false, false));
		write(genMax2(true, false));
		write(genMax2(false, true));
		write(genMax2(true, true));
		write(genMax2(true, true));
		write(genMax2(true, true));
		write(genRandImpossibleSimple(n, m));

		// for (int n : new int[]
		// { 5, 10, 100, 500, 1000, 2000 }) {
		// int m = Math.min(n * n / 2, 50000);
		// 1 write(genRandTest(n, m));
		// 2 write(genRandAntiGreedTest(n, m, 10));
		// 3 write(genConstFir(n, m, 10));
		// 4 write(genRandFir(n, m));
		// 5 write(genRandMultiFir(n, m, 3));
		// 6 write(genRandMultiFir(n, m, Math.min(n / 10, 300)));
		// 7 write(genRandAntiGreedMultiFir(n, m, 3));
		// 8 write(genRandAntiGreedMultiFir(n, m, Math.min(n / 10, 300)));
		// 9 write(genRandStick(n));
		// }
		// write(genMax1(false));
		// write(genMax1(true));
		// write(genMax2(false, false));
		// write(genMax2(true, false));
		// write(genMax2(false, true));
		// write(genMax2(true, true));
	}

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