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

class Pair<F, S> {
    public F first;
    public S second;
    public Pair(F f, S s) {
        this.first = f;
        this.second = s;
    }
}

class Dsu {
    private int[] p;
    private int[] rank;

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

    public int root(int v) {
        if (v == p[v])
            return v;
        p[v] = root(p[v]);
        return p[v];
    }

    public boolean join(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (rank[x] < rank[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        p[y] = x;
        if (rank[x] == rank[y]) ++rank[x];
        return true;
    }
}

class Tree {
    private ArrayList<ArrayList<Pair<Integer, Edge> > > g;
    private int degree[];
    private Edge[] edges;
    private int ptr = 0;

    static class Edge {
        public int from;
        public int to;
        public int l;
        public int t;
        public Edge edge;

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

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

        public void setEdge(Edge e) {
            edge = e;
        }
    }

    public Tree(int n) {
        edges = new Edge[n - 1];
        g = new ArrayList<ArrayList<Pair<Integer, Edge>>>();
        degree = new int[n];
        for (int i = 0; i < n; ++i)
            g.add(new ArrayList<Pair<Integer, Edge>>());
    }

    public Edge[] getEdges() {
        if (ptr != g.size() - 1)
            throw new RuntimeException("Incorrect structure of tree!");
        return edges;
    }

    public int getNumVertexes() {
        return g.size();
    }

    public void addEdge(int from, int to) {
        degree[from]++;
        degree[to]++;
        edges[ptr++] = new Edge(from, to);
        g.get(from).add(new Pair<Integer, Edge>(to, edges[ptr - 1]));
        g.get(to).add(new Pair<Integer, Edge>(from, edges[ptr - 1]));
    }

    public void addEdge(int from, int to, int l, int t) {
        degree[from]++;
        degree[to]++;
        edges[ptr++] = new Edge(from, to, l, t);
        g.get(from).add(new Pair<Integer, Edge>(to, edges[ptr - 1]));
        g.get(to).add(new Pair<Integer, Edge>(from, edges[ptr - 1]));
    }

    public int getDegree(int v) {
        return degree[v];
    }

    public ArrayList<ArrayList<Pair<Integer, Edge>>> getGraph() {
        return g;
    }
}

public class TestGen {
    int testCount, subtaskCount;
    PrintWriter testsDesc;
    Random random = new Random(0xDEAD);
    public static int MX_N = 100000;
    public static int MX_L = 10000;
    public static int MX_T = 1000000000;

    public void write(Tree tree, String folder, String subtask, int points, String comment) throws IOException {
        String path = String.format("../%s/%02d", folder, ++testCount);
        PrintWriter out = new PrintWriter(path);
        out.println(tree.getNumVertexes());
        Tree.Edge[] ed = tree.getEdges();
        if (ed.length != tree.getNumVertexes() - 1)
            throw new RuntimeException("Wrong number of edges!");
        tree = randomColoring(tree);
        ArrayList <Tree.Edge> edges = new ArrayList<Tree.Edge>();
        for (Tree.Edge e : ed)
            edges.add(e);
        for (Tree.Edge e : edges)
            if (random.nextBoolean()) {
                int tmp = e.from;
                e.from = e.to;
                e.to = tmp;
            }
        Collections.shuffle(edges, random);

        for (int i = 0; i < edges.size(); ++i)
            if (i + 1 == edges.size())
                out.println(edges.get(i).from + " " + edges.get(i).to + " " + edges.get(i).l + " " + edges.get(i).t);
            else
                out.println(edges.get(i).from + " " + edges.get(i).to + " " + edges.get(i).l + " " + edges.get(i).t);
        out.close();
        testsDesc.println(String.format("%s, folder=%s, subtask=%s, points=%d, comment=\"%s\"", path, folder, subtask, points, comment));
        System.out.println(String.format("Test %d is generated", testCount));
    }

    void genPreliminary() throws IOException {
        Tree tree1 = new Tree(5);
        tree1.addEdge(0, 1, 3, 2);
        tree1.addEdge(2, 0, 2, 3);
        tree1.addEdge(2, 3, 1, 2);
        tree1.addEdge(2, 4, 2, 4);
        write(tree1, "preliminary", "subtask0", 0, "sample1");

        Tree tree2 = new Tree(7);
        tree2.addEdge(1, 6, 4, 6);
        tree2.addEdge(2, 5, 4, 4);
        tree2.addEdge(2, 4, 4, 5);
        tree2.addEdge(0, 2, 3, 4);
        tree2.addEdge(1, 3, 2, 4);
        tree2.addEdge(0, 1, 3, 3);
        write(tree2, "preliminary", "subtask0", 0, "sample2");
        testCount = 0;
    }

    public ArrayList<Integer> genRandomShuffle(int n) {
        ArrayList<Integer> p = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i)
            p.add(i);
        Collections.shuffle(p, random);
        return p;
    }

    public Tree coloringTree(Tree tree, ArrayList <Integer> coloring) {
        Tree.Edge edges[] = tree.getEdges();
        int j = 0;
        for (Tree.Edge e : edges) {
            e.from = coloring.get(e.from) + 1;
            e.to = coloring.get(e.to) + 1;
        }
        return tree;
    }

    public Tree randomColoring(Tree tree) {
        boolean alreadyColoring = false;
        Tree.Edge[] edges = tree.getEdges();

        int n = tree.getNumVertexes();
        for (Tree.Edge e : edges)
            alreadyColoring |= e.from == n || e.to == n;
        if (!alreadyColoring)
            tree = coloringTree(tree, genRandomShuffle(tree.getNumVertexes()));
        return tree;
    }

    public Tree genBinaryStructure(int n) {
        Tree tree = new Tree(n);
        int i;
        for (i = 0; 2 * i + 2 < n; ++i) {
            tree.addEdge(i, 2 * i + 1);
            tree.addEdge(i, 2 * i + 2);
        }
        i = 2 * i + 1;
        for (; i < n; ++i)
            tree.addEdge(random.nextInt(i), i);
        return tree;
    }

    public Tree genRandomWithBigDiameter(int n) {
        Tree tree = new Tree(n);
        Dsu dsu = new Dsu(n);
        int edges = 0;
        while (edges < n - 1) {
            int x = random.nextInt(n);
            int y = random.nextInt(n);
            if (dsu.join(x, y)) {
                ++edges;
                tree.addEdge(x, y);
            }
        }
        return tree;
    }

    public Tree genRandomWithManyListsStructure(int n) {
        Tree tree = new Tree(n);
        for (int i = 1; i < n; ++i)
            tree.addEdge(random.nextInt(i), i);
        return tree;
    }

    public Tree genLongTreeStructure(int n, int ridgeLen) {
        Tree tree = new Tree(n);
        for (int i = 0; i + 1 < ridgeLen; ++i)
            tree.addEdge(i, i + 1);
        for (int i = ridgeLen; i < n; ++i)
            tree.addEdge(random.nextInt(i), i);
        return tree;
    }

    public Tree genNBranchesStructure(int n, int branches) {
        if (n - 1 < branches)
            throw new RuntimeException("Too much branches!");
        Tree tree = new Tree(n);
        int len = (n - 1) / branches;
        int v = 1;
        for (int i = 0; i < branches && v < n; ++i) {
            tree.addEdge(0, v++);
            for (int j = 1; j < len && v < n; ++j, ++v)
                tree.addEdge(v - 1, v);
        }
        if (v < n) {
            tree.addEdge(v, len);
            ++v;
            while (v < n)
                tree.addEdge(v - 1, v++);
        }
        return tree;
    }

    public Tree genBoneStructure(int middle, int left, int right) {
        Tree tree = new Tree(middle + left + right);
        for (int i = 0; i + 1 < middle; ++i)
            tree.addEdge(i, i + 1);
        for (int i = middle; i < middle + left; ++i)
            tree.addEdge(0, i);
        for (int i = middle + left; i < middle + left + right; ++i)
            tree.addEdge(middle - 1, i);
        return tree;
    }


    public Tree setParameterOneVertexGood(Tree tree) {
        tree = setParameterUselessActiveRun(tree, MX_L, new int[] {1});
        int n = tree.getNumVertexes();
        Tree.Edge[] edges = tree.getEdges();
        Tree.Edge edge = null;
        int list = -1;
        for (int i = 0; i < n; ++i)
            if (tree.getDegree(i) == 1) {
                list = i;
                break;
            }
        for (Tree.Edge e : edges)
            if (e.to == list || e.from == list) {
                edge = e;
                break;
            }
        edge.t = random.nextInt(2 * n) + 1;
        ArrayList <Integer> colors = genRandomShuffle(n);
        if (random.nextBoolean()) {
            for (int i = 0; i < colors.size(); ++i)
                if (colors.get(i) == 0) {
                    int tmp = colors.get(list);
                    colors.set(list, 0);
                    colors.set(i, tmp);
                    break;
                }
        }
        return coloringTree(tree, colors);
    }

    //100 100 1000; 1000 10000 100000; 1000, 500 10000; 10000, 5000, 1000000; 100000, 10^7
    public Tree setParametersOfEdgesWithConstraints(Tree tree, int MAX_L, int MIN_T, int MAX_T) {
        Tree.Edge[] edges = tree.getEdges();
        for (Tree.Edge e : edges) {
            e.l = random.nextInt(MAX_L) + 1;
            e.t = random.nextInt(MAX_T - MIN_T + 1) + MIN_T;
        }
        return tree;
    }

    public Tree setParametersAddActivityRun(Tree tree) {
        int n = tree.getNumVertexes();
        setParametersOfEdgesWithConstraints(tree, MX_L, 1, MX_L * 10);
        ArrayList <Integer> nonList = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i)
            if (tree.getDegree(i) != 1)
                nonList.add(i);
        if (nonList.size() == 0)
            throw new RuntimeException("Incorrect numbers of non list vertexes");
        //System.err.println("non list = " + nonList.size());
        int iteration = n / 10;
        int sumPath = 0;
        for (int it = 0; it < iteration && sumPath <= 8600000; ++it) {
            int v = nonList.get(random.nextInt(nonList.size()));
            int lPath = push(v, tree.getGraph());
            sumPath += lPath;
        }
        return tree;
    }

    public int push(int v, ArrayList<ArrayList<Pair<Integer, Tree.Edge>>> g) {
        int len = 0;
        int p = -1, l = 0;
        for (int i; g.get(v).size() != 1; ++l) {
            do {
                i = random.nextInt(g.get(v).size());
            } while (g.get(v).get(i).first == p);
            len += g.get(v).get(i).second.l;
            g.get(v).get(i).second.t = Math.max(g.get(v).get(i).second.t, len);
            p = v;
            v = g.get(v).get(i).first;
        }
        return l + 1;
    }

    public Tree setParameterUselessActiveRun(Tree tree, int MAX_L, int[] T) {
        Tree.Edge[] allEdges = tree.getEdges();
        for (Tree.Edge e : allEdges) {
            e.l = Math.min(MX_L, random.nextInt(MAX_L) + 2);
            if (tree.getDegree(e.from) == 1 || tree.getDegree(e.to) == 1)
                e.t = T[random.nextInt(T.length)];
            else
                e.t = MX_T - random.nextInt(1000);
        }
        return tree;
    }

    public void genHandleTests(int mx, int points) throws IOException {
        write(new Tree(1), "tests", "subtask1", 0, "n = 1");

        Tree two = new Tree(2);
        two.addEdge(0, 1, 1, 1);
        write(two, "tests", "subtask1", 0, "n = 2");

        Tree two2 = new Tree(2);
        two2.addEdge(0, 1, 2, 1);
        write(two, "tests", "subtask1", 0, "n = 2");
    }

    public void genSubtask(int mx, int points) throws IOException {
        ++subtaskCount;
        String subtask = "subtask" + Integer.toString(subtaskCount);
        int sq = (int)Math.sqrt(mx);
        int[] USELESS_ARRAY1 = new int[] {1};
        int[] USELESS_ARRAY2 = new int[]{1, MX_T};

        write(setParameterUselessActiveRun(genBinaryStructure(mx), MX_L, USELESS_ARRAY1), "tests", subtask, 0, "binary structure with useless activity");
        write(setParameterUselessActiveRun(genBinaryStructure(mx), MX_L, USELESS_ARRAY2), "tests", subtask, 0, "binary structure with useless2 activity");
        write(setParametersOfEdgesWithConstraints(genBinaryStructure(mx), MX_L, 1, MX_L * 10), "tests", subtask, 0, "binary structure with constraints  ti in [1; 10^5]");

        write(setParametersOfEdgesWithConstraints(genNBranchesStructure(mx, sq), MX_L, 1, MX_L * 10), "tests", subtask, 0, "sqrt branches with constraints  ti in [1; 10^5]");
        write(setParametersOfEdgesWithConstraints(genNBranchesStructure(mx, mx / 100), MX_L / 10, MX_L / 20, MX_L), "tests", subtask, 0, "mx / 100 branches with constraints  ti in [500; 10^4]");
        write(setParametersOfEdgesWithConstraints(genNBranchesStructure(mx, 10), MX_L, MX_L / 20, MX_L * 10), "tests", subtask, 0, "10 branches with constraints  ti in [1; 10^5]");
        write(setParametersOfEdgesWithConstraints(genNBranchesStructure(mx, 30), MX_L, MX_L / 2, 1000000), "tests", subtask, 0, "30 branches constraints  ti in [500; 10^6]");
        write(setParametersAddActivityRun(genNBranchesStructure(mx, sq)), "tests", subtask, 0, "sq branches with add some active run");
        write(setParametersAddActivityRun(genNBranchesStructure(mx, sq)), "tests", subtask, 0, "sq branches with add some active run");
        //write(setParametersAddActivityRun(genNBranchesStructure(mx, sq)), "tests", subtask, 0, "sq branches with add some active run");
        //TODO something

        write(setParametersOfEdgesWithConstraints(genRandomWithBigDiameter(mx), MX_L, 1, MX_L * 10), "tests", subtask, 0, "big diameter with constraints  ti in [1; 10^5]");
        write(setParametersOfEdgesWithConstraints(genRandomWithBigDiameter(mx), MX_L, 1, MX_T / 100), "tests", subtask, 0, "big diameter with constraints  ti in [1; 10^7]");
        write(setParametersOfEdgesWithConstraints(genRandomWithBigDiameter(mx / 2), MX_L, 1, MX_T), "tests", subtask, 0, "big diameter with constraints  ti in [1; 10^9]");
        write(setParameterUselessActiveRun(genRandomWithBigDiameter(mx), MX_L, USELESS_ARRAY1), "tests", subtask, 0, "big diameter with useless activity");
        write(setParameterOneVertexGood(genRandomWithBigDiameter(mx)), "tests", subtask, 0, "big diameter with one good list");

        write(setParameterUselessActiveRun(genRandomWithManyListsStructure(mx), MX_L, USELESS_ARRAY1), "tests", subtask, 0, "many lists with useless activity");
        write(setParameterUselessActiveRun(genRandomWithManyListsStructure(mx), 1, USELESS_ARRAY2), "tests", subtask, 0, "many lists with useless2 activity and li=1");
        write(setParameterUselessActiveRun(genRandomWithManyListsStructure(mx), MX_L, USELESS_ARRAY1), "tests", subtask, 0, "many lists with useless2 activity");
        write(setParameterOneVertexGood(genRandomWithManyListsStructure(mx)), "tests", subtask, 0, "many lists with one good list");
        write(setParametersOfEdgesWithConstraints(genRandomWithManyListsStructure(mx), MX_L, 1, MX_T / 1000), "tests", subtask, 0, "many lists with constraints ti in [1; 10^9]");
        //write(setParametersOfEdgesWithConstraints(genRandomWithManyListsStructure(mx), MX_L, 1, MX_T / 100), "tests", subtask, 0, "many lists with constraits ti in [1; 10^7]");

        write(setParameterUselessActiveRun(genLongTreeStructure(mx, mx), MX_L, USELESS_ARRAY1), "tests", subtask, 0, "long tree with useless active");
        write(setParameterOneVertexGood(genLongTreeStructure(mx, mx / 2)), "tests", subtask, 0, "long tree with one good");
        write(setParametersAddActivityRun(genLongTreeStructure(mx, mx)), "tests", subtask, 0, "long tree with some activity");
        write(setParametersAddActivityRun(genLongTreeStructure(mx, mx / 2)), "tests", subtask, 0, "long tree with some activity");
        write(setParametersOfEdgesWithConstraints(genLongTreeStructure(mx, mx / 2), MX_L, 1, MX_T / 100), "tests", subtask, 0, "many lists with constraints ti in [1; 10^7]");
        write(setParametersOfEdgesWithConstraints(genLongTreeStructure(mx, mx - 20), MX_L, 1, MX_L * 10), "tests", subtask, 0, "long tree with constraints  ti in [1; 10^5]");
        
        write(setParameterOneVertexGood(genBoneStructure(mx - 10, 10, 0)), "tests", subtask, 0, "like bone tree with one good vertex");
        write(setParameterOneVertexGood(genBoneStructure(mx - 10, 10, 0)), "tests", subtask, 0, "like bone tree with one good vertex");
        write(setParametersAddActivityRun(genBoneStructure(mx / 3, mx / 3, mx / 3)), "tests", subtask, 0, "like bone tree with some add some activity");
        write(setParametersAddActivityRun(genBoneStructure(mx - 20, 10, 10)), "tests", subtask, 0, "like bone tree with add some activity");

        testsDesc.println(String.format("comment_subtask%d=\"n &lt;= %d\"", subtaskCount, mx));
        testsDesc.println(String.format("bonus_subtask%d=%d", subtaskCount, points));
    }

    public void run() throws IOException {
        new File("../preliminary").mkdir();
        new File("../tests").mkdir();
        testsDesc = new PrintWriter("../tests.desc");

        genPreliminary();
        genHandleTests(1000, 40);
        genSubtask(1000, 40);
        genSubtask(MX_N, 60);

        testsDesc.close();
    }

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