TopologicalOrdering

Given a directed graph, a topological ordering of its vertices is a permutation P of its vertices with the following property: whenever the graph contains an edge from vertex u to vertex v, the vertex u appears in P before the vertex v.


It is known that computing the number of topological orderings in a given directed graph is hard (in particular, #P-complete). In this task we will take a look at the inverse problem: given n, find any directed graph with exactly n different topological orderings.


Here is a precise definition of our task: You are given an int n. Construct a graph that satisfies the following constraints:

• The graph must have exactly n different topological orderings.
• The number of vertices in the graph must be between 1 and 50, inclusive.
• The vertices must be numbered 0 through x-1, where x is the number of vertices.
• The number of edges in the graph must be between 0 and 100, inclusive.
• There must not be any self-loops.
• There must not be any duplicate edges. (I.e., for each ordered pair of vertices (u,v), there must be at most one edge from u to v.)

You may assume that for the given constraints a solution always exists. If there are multiple solutions, you may choose any of them. Return a int[] that contains the number of vertices in your graph followed by a list of its edges.


Formally, the correct return value should be constructed as follows: Suppose that your graph has x vertices and y edges. Let a[] and b[] be such that for each valid i your graph contains an edge from vertex a[i] to vertex b[i]. Then, return the following int[]: {x, a[0], b[0], a[1], b[1], ..., a[y-1], b[y-1] }.