BearSpans

Bear Limak loves algorithms and tolerates data structures. Today he learned about Boruvka's algorithm. Boruvka's algorithm was the first polynomial-time algorithm to find the minimum spanning tree (MST). Moreover, it was pretty efficient because it worked in O(E log V). You can find a detailed description of this algorithm and its history at https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm. Below we give a short description of Boruvka's algorithm. This description should be used when solving this problem.

The input for Boruvka's algorithm is a simple connected undirected weighted graph G. (Here, "simple" means there are no loops and each pair of vertices is directly connected by at most one edge.) The edge weights are distinct positive integers from 1 to m, where m is the number of edges in the graph.

The minimum spanning tree of G is a subgraph H of G with the following properties:

• H contains the same vertices as G.
• H is connected.
• The sum of weights of edges in H is as small as possible.

Here is Boruvka's algorithm in pseudocode:

Initialize H to contain all vertices of G but no edges at all.

While H is not connected yet:
    For each component C in H:
        Find the lightest edge in G that has exactly one endpoint in C.
        Mark this edge for addition.

    Add all marked edges to H.

Return H.

Note that the algorithm is deterministic: the weights are all distinct, hence each edge we mark for addition is uniquely determined.

You are given ints n, m, and k. Your task is to construct one arbitrary graph G with the following properties:

• G is a valid input for Boruvka's algorithm, as defined above.
• G has exactly n vertices and m edges. The vertices are numbered 1 through n. The edge weights are 1 through m.
• Boruvka's algorithm will find the MST of G in exactly k rounds. (A round is a single iteration of the while-cycle in the pseudocode above.)

If no such G exists, return the int[] {-1}. (That is, a int[] with a single element that is minus one.)

Otherwise, return a int[] with the description of your chosen G. This int[] should have 2*m elements: two for each edge. Let answer[] denote the returned int[]. For each w between 1 and m, inclusive, take the edge with weight w and store its endpoints into answer[2*w-2] and answer[2*w-1].