Under construction

Still being built. Things may change

Graph decomposition

Time limit2sMemory limit1024 MB

Summary
Given n and a partition of 2n-1 into parts a_i, output edge sets of K_{2n} so that each set is an a_i-factor and every edge appears in exactly one set.
Level

Medium7 of 10

Topics
Graph, Combinatorics, Math
Solved
No attempts yet

Problem

Consider an undirected graph GG. An rr-factor of GG is a subgraph that contains all vertices of GG and some subset of the edges of GG, such that every vertex has degree rr. Such a graph is called rr-regular.

Let GG be a kk-regular graph, and let λ\lambda be a partition of kk into parts: k=a1+a2+…+amk = a_1 + a_2 + \ldots + a_m. A λ\lambda-decomposition of GG is a set of graphs G1,G2,…,GmG_1, G_2, \ldots, G_m such that each GiG_i is an aia_i-factor of GG, and every edge of GG belongs to exactly one of the graphs GiG_i.

For the complete graph K2nK_{2n} with an even number of vertices and a partition λ\lambda of 2n−12n-1 into parts, construct a λ\lambda-decomposition of K2nK_{2n}.

Input

The first line contains an integer nn (1≤n≤1001 \le n \le 100). The second line contains an integer mm, followed by the numbers a1,a2,…,ama_1, a_2, \ldots, a_m (1≤ai≤2n−11 \le a_i \le 2n-1, ∑ai=2n−1\sum a_i = 2n-1).

Output

Print mm descriptions of graphs. The description of GiG_i must contain nain a_i edges. Separate the graph descriptions with blank lines.

Examples1

  1. Example 1

    Input
    3
    3 1 2 2
    
    Expected output
    1 4
    2 5
    3 6
    
    1 2
    2 3
    3 4
    4 5
    5 6
    6 1
    
    1 3
    3 5
    5 1
    2 4
    4 6
    6 2