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

public class TestGen {
	public static void main(String[] args) throws IOException {
		new TestGen().run();
	}

	BufferedReader br;
	StringTokenizer in;
	PrintWriter out;

	public String nextToken() throws IOException {
		while (in == null || !in.hasMoreTokens()) {
			in = new StringTokenizer(br.readLine());
		}
		return in.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	int tNumber, tPre;
	Random rnd;
	final int MAXN = 100000;
	final int MAXC = 10001;

	class edge {
		int v, u, cost, type;

		public edge(int v, int u, int cost, int type) {
			super();
			this.v = v;
			this.u = u;
			this.cost = cost;
			this.type = type;
		}
	}

	void printPre(int n, ArrayList<edge> edges) throws IOException {
		System.err.println(tPre);
		if (tPre < 10) {
			out = new PrintWriter("../preliminary/0" + tPre);
		} else {
			out = new PrintWriter("../preliminary/" + tPre);
		}
		tPre++;
		assert n == edges.size() + 1;
		out.println(n);
		for (int i = 0; i < edges.size(); i++) {
		    edge e = edges.get(i);
			out.println(e.v + " " + e.u + " " + e.cost + " " + e.type);
		}
		out.close();
	}

	void print(int n, ArrayList<edge> edges) throws IOException {
		System.err.println(tNumber);
		if (tNumber < 10) {
			out = new PrintWriter("../tests/0" + tNumber);
		} else {
			out = new PrintWriter("../tests/" + tNumber);
		}
		tNumber++;
		assert n == edges.size() + 1;
		out.println(n);
		for (int i = 0; i < edges.size(); i++) {
		    edge e = edges.get(i);
			out.println(e.v + " " + e.u + " " + e.cost + " " + e.type);
		}
		out.close();
	}

	public void genMinTests() throws IOException {
	    ArrayList<edge> test = new ArrayList<>();
	    print(1, test);

	    test.add(new edge(1, 2, 3, 1));
	    print(2, test);

	    test.set(0, new edge(1, 2, 3, 0));
	    print(2, test);
	}

    public void genRandomTest(int n) throws IOException {
        ArrayList<Integer> vs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            vs.add(i);
        }
        Collections.shuffle(vs);

        ArrayList<edge> edges = new ArrayList<>();
        for (int i = 1; i < n; i++) {
          int index = rnd.nextInt(i);
          edges.add(new edge(vs.get(index) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), rnd.nextInt(2)));
        }
        print(n, edges);
    }

    public void genBamboo(int n) throws IOException {
        ArrayList<Integer> vs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            vs.add(i);
        }
        Collections.shuffle(vs);

        ArrayList<edge> edges = new ArrayList<>();
        if (rnd.nextInt(2) == 0) {
            for (int i = 1; i < n; i++) {
                edges.add(new edge(vs.get(i - 1) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), rnd.nextInt(2)));
            }
        } else {
            for (int i = 1; i < n; i++) {
                edges.add(new edge(vs.get(i - 1) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), 1));
            }
        }
        print(n, edges);
    } 

    public void genBambooWithTrash(int n) throws IOException {
        ArrayList<Integer> vs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            vs.add(i);
        }
        Collections.shuffle(vs);

        ArrayList<edge> edges = new ArrayList<>();
        if (rnd.nextInt(2) == 0) {
            for (int i = 1; i < n / 2; i++) {
                edges.add(new edge(vs.get(i - 1) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), rnd.nextInt(2)));
            }
            for (int i = n / 2; i < n; i++) {
              int index = rnd.nextInt(i);
              edges.add(new edge(vs.get(index) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), rnd.nextInt(2)));
            }
              
        } else {
            for (int i = 1; i < n / 2; i++) {
                edges.add(new edge(vs.get(i - 1) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), 1));
            }
            for (int i = n / 2; i < n; i++) {
              int index = rnd.nextInt(i);
              edges.add(new edge(vs.get(index) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), 1));
            }
        }
        print(n, edges);
    }

    public void genAllZeroes(int n) throws IOException {
        ArrayList<Integer> vs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            vs.add(i);
        }
        Collections.shuffle(vs);

        ArrayList<edge> edges = new ArrayList<>();
        for (int i = 1; i < n; i++) {
          int index = rnd.nextInt(i);
          edges.add(new edge(vs.get(index) + 1, vs.get(i) + 1, rnd.nextInt(MAXC), 0));
        }
        print(n, edges);
    }

	public void generate() throws IOException {
		new File("../tests").mkdir();
		new File("../preliminary").mkdir();
		tNumber = 1;
		tPre = 1;
		rnd = new Random(3131313);
		genSamples();

		//First group of tests (01-19)
		genMinTests();                      //3 tests
		for (int i = 0; i < 5; i++)
		    genRandomTest(100);             //5 tests
		for (int i = 0; i < 5; i++)
    		genBamboo(100);                 //5 tests
		for (int i = 0; i < 5; i++)
    		genBambooWithTrash(100);        //5 tests
    	genAllZeroes(100);                  //1 test

	    //Second group of tests (20-35)
		for (int i = 0; i < 5; i++)
		    genRandomTest(3000);            //5 tests
		for (int i = 0; i < 5; i++)
    		genBamboo(3000);                //5 tests
		for (int i = 0; i < 5; i++)
    		genBambooWithTrash(3000);       //5 tests
    	genAllZeroes(3000);                 //1 test

	    //Third group of tests (36-51)
		for (int i = 0; i < 5; i++)
		    genRandomTest(MAXN);            //5 tests
		for (int i = 0; i < 5; i++)
    		genBamboo(MAXN);                //5 tests
		for (int i = 0; i < 5; i++)
    		genBambooWithTrash(MAXN);       //5 tests
    	genAllZeroes(MAXN);                 //1 test

	}

	private void genSamples() throws IOException {
	    int n = 3;
		ArrayList<edge> test = new ArrayList<>();
		test.add(new edge(1, 2, 1, 1));
		test.add(new edge(1, 3, 1, 1));
		printPre(n, test);

		test = new ArrayList<>();
		test.add(new edge(1, 2, 1, 1));
		test.add(new edge(1, 3, 2, 0));
		printPre(n, test);
	}                      

	public void run() throws IOException {
		Locale.setDefault(Locale.US);
		generate();
	}
}
