MinimumCutsAgain

In this problem you will be constructing a simple weighted directed graph.

A 0-1 cut in the graph is a subset S of vertices that does contain the vertex 0 but does not contain the vertex 1. Let T be the complement of S. The size of the cut is the total weight of all edges that lead from S to T. (The weight of edges from T to S does not matter.) A 0-1 cut is called a minimum 0-1 cut if its size is the smallest among all 0-1 cuts.

You are given an int n. Construct any undirected graph with the following properties:

• The number of vertices must be between 2 and 20, inclusive.
• The vertices must be numbered 0 through v-1, where v is their number.
• The graph must be simple - i.e., no self-loops and no multiple edges going in the same direction. (However, for any distinct x,y the graph may contain both an edge from x to y and an edge from y to x.)
• All edge weights must be integers between 1 and 10^9, inclusive.
• The graph must have exactly n different minimum 0-1 cuts.

Suppose the graph you constructed has v vertices and e edges. Return a int[] with 1 + 3*e elements. Element 0 of the return value should be the number v of vertices. The rest of the return value should be a list of edges. For each edge i, give its source vertex s_i, its destination vertex t_i, and its weight w_i. That is, the return value should be formatted as follows: { v, s₀, t₀, w₀, s₁, t₁, w₁, ... }.

If there are multiple correct solutions, you may output any of them.