Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Valera had an undirected connected graph without self-loops and multiple edges…

  1. User

    Valera had an undirected connected graph without self-loops and multiple edges consisting of n vertices. The graph had an interesting property: there were at most k edges adjacent to each of its vertices. For convenience, we will assume that the graph vertices were indexed by integers from 1 to n.

    One day Valera counted the shortest distances from one of the graph vertices to all other ones and wrote them out in array d. Thus, element d[i] of the array shows the shortest distance from the vertex Valera chose to vertex number i.

    Then something irreparable terrible happened. Valera lost the initial graph. However, he still has the array d. Help him restore the lost graph. Input

    The first line contains two space-separated integers n and k (1 ≤ k < n ≤ 105). Number n shows the number of vertices in the original graph. Number k shows that at most k edges were adjacent to each vertex in the original graph.

    The second line contains space-separated integers d[1], d[2], ..., d[n] (0 ≤ d[i] < n). Number d[i] shows the shortest distance from the vertex Valera chose to the vertex number i.

    Output

    If Valera made a mistake in his notes and the required graph doesn't exist, print in the first line number -1. Otherwise, in the first line print integer m (0 ≤ m ≤ 106) — the number of edges in the found graph.

    In each of the next m lines print two space-separated integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), denoting the edge that connects vertices with numbers ai and bi. The graph shouldn't contain self-loops and multiple edges. If there are multiple possible answers, print any of them.

    Examples

    Input

    3 2 0 1 1

    Output

    3 1 2 1 3 3 2

    Input

    4 2 2 0 1 3

    Output

    3 1 3 1 4 2 3

    Input

    3 1 0 0 0

    Output

    -1

  2. DeepSeek Assistant

    We need to reconstruct an undirected connected graph with n vertices, maximum degree per vertex ≤ k, given distances from some source vertex (unknown which one) to all vertices, in array d[1..n]. We must output any graph (edges) that satisfies:

    • The graph is connected.
    • No self-loops, no multiple edges.
    • For each vertex v, deg(v) ≤ k.
    • The shortest distances from some vertex (say s) to all others are exactly the given d[i]. (Note: d[i] are the distances from the chosen vertex, but we don't know which vertex is the source. However, the array d is relative to that source. So we must find a graph such that there exists a vertex s with distances d[i] exactly. The problem says: "Valera counted the shortest distances from one of the graph vertices to all other ones and wrote them out in array d. Thus, element d[i] shows the shortest distance from the vertex Valera chose to vertex number i." So the source is not given; it's implicit. Usually, in such problems, we can assume the source is vertex with d=0. But careful: The array d[1..n] is provided; there should be exactly one vertex with d=0? Possibly yes, because distance from source to itself is 0. Could there be multiple vertices with d=0? That would mean they are all at distance 0 from source, which can only happen if they are the source itself; but there is only one source. So there should be exactly one vertex with d=0. However, the input constraints allow any d[i] < n, no guarantee it's valid. So if there are multiple zeros, it's impossible because distance from a single source to distinct vertices can't both be 0. So we can check that exactly one vertex has d=0. Actually, it's possible that the source is vertex i and d[i]=0, for exactly one i. But could there be multiple vertices with d=0 if the graph has loops? No loops, and distances are shortest path lengths, so distinct vertices must have distance >0 unless they are the same vertex. So indeed exactly one zero is necessary. So we can check that.

    Also, distances must satisfy triangle inequality: for any two vertices u, v, |d[u]-d[v]| ≤ dist(u,v) ≤ d[u]+d[v], but we don't have explicit distances; we need to construct a graph where those distances hold exactly the given d. Usually we can try to construct a tree or a graph with some extra edges.

    Given the degree constraint, we need to keep degrees ≤ k.

    Common approach for such problems: The distances define a BFS tree rooted at the source (vertex with d=0). The BFS tree edges are between vertices with distances that differ by 1. The BFS tree ensures distances are at most the tree distance (which equals depth). However, the BFS tree might not satisfy degree constraints; we might need to add extra edges to satisfy connectivity? Actually, the BFS tree itself is a tree connecting all vertices with edges (parent-child) that are between distance d and d+1. That yields a graph that has exactly distances as given if we ensure that there are no shorter paths via non-tree edges. But if we only include BFS tree edges, then distances from source are exactly the depth because BFS tree is a shortest path tree if we construct it appropriately? Actually, if we take any vertex v, its depth = d[v] if we set its parent to be any neighbor with distance d[v]-1. However, we must ensure that no alternative path can give a shorter distance than d[v]. In a BFS tree, the distance is exactly the depth because each edge is between vertices whose depths differ by at most something. But there's a nuance: In a tree, the unique path from root to v has length equal to depth (number of edges). That length is at least the distance; but if the tree is constructed from a valid distance array, then we can assign each vertex (except root) a parent with distance exactly one less. Then the distance in that tree will be exactly d[v] if there are no edges that create a shortcut. However, we must ensure that we don't accidentally create a shorter path via cross edges. If we add only tree edges, the distances are the depths. But we might need to add extra edges to meet the degree constraint? Actually, the degree constraint is maximum degree ≤ k. We need to construct a graph (any graph) meeting constraints, not necessarily a tree. But a tree can be built, and if the tree already satisfies degree constraints (i.e., each vertex's number of children plus maybe parent <= k), then we can output the tree. However, the tree might violate degree constraints if some vertex has too many neighbors (children) because the parent also counts as neighbor. So we need to ensure that for each vertex, its degree (including parent and children) ≤ k. If the tree violates that, maybe we can add extra edges to reduce degree? Actually adding edges increases degree, not reduces. So if tree already exceeds k at some vertex, we cannot reduce it by adding edges; we would need to find a different graph that still satisfies distances. So we need to consider if there exists any graph meeting degree constraint and distances.

    The problem asks to output any graph if possible; otherwise -1.

    We need to determine conditions for existence and construct a graph.

    Observation: The distances from root must satisfy certain properties. The source vertex s with d=0. Let L_t = set of vertices with distance t. For the graph to be connected and distances correct, we must have edges only between vertices whose distances differ by at most 1? Actually, consider any edge (u, v). The triangle inequality gives |d[u]-d[v]| ≤ 1? Not necessarily. If there is an edge between vertices with distance difference >1, say d[u]=a, d[v]=b with |a-b| ≥ 2, then the distance from s to the farther vertex could be at most the distance to the closer plus 1, i.e., d[v] ≤ d[u] + 1. But if a-b ≥2, then the distance from s to v would be at most a+1, but we have d[v]=b which is less than a-1? Actually if a > b+1, then d[u] > d[v] + 1. Then from s to u: there is a path s->...->v->u of length d[v]+1, which is ≤ b+1, which is < a, contradicting that d[u] is shortest distance. So any edge must satisfy |d[u]-d[v]| ≤ 1. So edges can only be between vertices of same distance (same layer) or adjacent layers (difference 1). That's a necessary condition.

    Also, if there is an edge between two vertices in same layer t, then there would be a path from s to either of length t, which is fine; but that edge could create alternative paths but not shorter than t because any path using that edge would have at least t? Actually could it create a shorter path to some vertex? Possibly if there is an edge between two vertices both at distance t, that doesn't affect distances from s to them because they already have distance t. However, it could potentially give a shorter path to other vertices? For a vertex at distance t+1, maybe it can go via the same-layer edge? Consider a vertex w with d[w]=t+1; if there is an edge between two vertices u and v at distance t, could there be a path to w shorter than t+1? Possibly if w is adjacent to u, distance would be t+1; if also adjacent to v, same. No shorter. So it's fine.

    Thus, the graph can be built with edges only within layers (t) and between layers (t and t+1). Also, the root layer has only root.

    Now, to satisfy distances, we need that for each vertex v with d[v] > 0, there is at least one neighbor u with d[u] = d[v] - 1. Because otherwise the shortest path from s would be longer than d[v] (since any path must go through some neighbor with distance one less, because edges only connect layers differing by at most 1; but could it go via same layer? That would not decrease distance; from s to any neighbor of v has distance either d[v] or d[v]-1 or d[v]+1. To get to v, you need to reach a vertex with distance d[v]-1 then go to v, because if you go via vertex with distance d[v], you would have distance at least d[v]+1? Actually if you go from s to u (d[u]=d[v]) then edge to v (d[v] could be d[v] or d[v]+1? Since edge only allows difference ≤1, v could be d[v] or d[v]±1? but if u has d[u]=d[v] then v could have d[v]±1? If v has d[v] and u has same, then edge is within same layer, then path s->...->u->v would have length at least d[v] + 1, so not shortest. So the only way to have a path of length d[v] is to have a neighbor with distance d[v]-1. So each vertex with d>0 must have at least one neighbor in the previous layer.

    Thus, necessary condition: For each distance value t > 0, each vertex in L_t must have at least one neighbor in L_{t-1}. In terms of construction, we can create edges from each vertex in L_t to some vertex in L_{t-1} to satisfy that.

    Now, the degree constraints: For each vertex, the number of neighbors ≤ k. This includes its connections to previous layer (parent), next layer (children), and same layer (peers). So we need to allocate edges such that all vertices have degrees ≤ k and each vertex in L_t (t>0) has at least one parent.

    Additionally, the graph must be connected. If we add edges ensuring each vertex (except root) has a parent in previous layer, then the graph becomes connected because there is a path to the root. However, note that the graph might have isolated components if some vertex in same layer only connects to same layer but not to previous? But we require each non-root vertex to have a parent, which ensures connectivity. So connectivity is automatically satisfied if we have that.

    Thus, a constructive approach: Build a BFS tree (or forest) by connecting each vertex to a parent in previous layer. Then also we may add extra edges (within layer or between layers) as long as degree constraints not exceeded. But we don't need extra edges unless we need to satisfy degree constraints? Actually, we only need to output some graph that satisfies the conditions; the minimal edges (just a tree) might be enough if degree constraints hold. However, if degree constraints are violated by the tree, we might need to adjust: maybe we can choose different parent assignments to distribute children more evenly. Because each vertex's degree includes its children count. So we can decide which vertices in L_{t-1} to connect to vertices in L_t. This is like a flow or assignment problem: we have sizes of layers, each vertex in L_t needs at least 1 edge to L_{t-1}. Each vertex in L_{t-1} can have up to (k - something) edges to L_t. But also vertices may have edges within same layer (optional) and to previous layer (just one required). Also vertices in L_{t-1} may have edges to L_{t-2} as well (their parent) which counts toward degree. So overall degree budget for each vertex is k.

    So we need to determine if we can assign parents to vertices (except root) such that for each vertex v in layer t (t>0), we select a parent u in layer t-1, and for all vertices u, the total number of children assigned to u (from layer t) plus (if u is not root, 1 for its own parent) plus any optional edges (we can choose to add none to keep degrees low) does not exceed k.

    Additionally, we might need to consider that vertices in same layer might need to be connected to satisfy something? No, not needed.

    Thus, existence reduces to: For each layer t from 1 to max_d, we need to assign each vertex in L_t to a parent in L_{t-1} such that each vertex u in L_{t-1} gets at most (k - deg_other(u)) children, where deg_other(u) includes edges to its parent (if t-1>0) and possibly edges we might add later? But we can plan the tree first. Since we haven't added any other edges, the only edges that contribute to degree are: For root (layer 0), it has only children (no parent). For any other vertex u in layer t (t>0), it has exactly one parent (to layer t-1) and some number of children (to layer t+1) that will be assigned later. So we need to consider the entire tree's degrees: For a vertex u, its degree in the final tree = (number of children assigned to it) + (1 if t>0 else 0). So the constraint is: for all u, children_u + (t>0 ? 1 : 0) ≤ k.

    Therefore, we need to check if we can assign children to parents layer by layer such that each vertex's total children count stays within its remaining capacity.

    We can treat this as a flow: For each layer t=0,1,..., D-1 (where D = max distance), we have a set of parents (size |L_t|) each with capacity c_t(u) = k - (1 if t>0 else 0) - (any previous children? Actually children from previous layer assignment? Wait, children are from vertices in L_t to L_{t+1}. So when we process layer t to assign children for L_{t+1}, we consider vertices in L_t as parents. Their degree so far: if t>0, they already have a parent edge (to L_{t-1}) and possibly children from earlier assignments? No, children from L_t to L_{t+1} are not assigned yet; but they may have been assigned as children from L_{t-1}? Actually each vertex only has one parent (incoming from previous layer) and some number of children (outgoing to next layer). So at the time of assigning children from L_t to L_{t+1}, the degree of a vertex u in L_t currently consists of: 1 if t>0 (parent edge) + possibly any edges we add intentionally within same layer? We won't add any such edges. So the remaining capacity for children is k - (t>0?1:0). However, we might also later add edges within same layer or cross-layer? But we don't need to add them, so we can keep the graph as a tree. So to satisfy the tree, we just need: For each u in L_t, number of children assigned to u ≤ k - (t>0?1:0). For root (t=0): capacity = k.

    But is it sufficient that we can assign parents for all vertices with these capacities? Let's check the root: must have enough capacity to accommodate all children from L_1? Actually L_1 vertices need parents in L_0. So we need |L_1| ≤ k * |L_0|? But wait, root is the only vertex in L_0? Not necessarily: There might be multiple vertices with distance 0? We argued that exactly one vertex should have d=0. So |L_0| = 1. So then we need |L_1| ≤ k (since root capacity = k). So that's a necessary condition.

    For t=1: Each vertex in L_1 will have at least one child? Not necessarily; they may have no children if L_2 is empty. But they must have capacity for children from L_2. So if |L_2| > total capacity of L_1 vertices, impossible. But also each L_2 vertex needs exactly one parent; we can assign them to any L_1 vertex as long as each L_1 vertex's number of children ≤ k - 1 (since they have a parent to root). So total capacity of L_1 is |L_1| * (k-1). So need |L_2| ≤ |L_1| * (k-1).

    Similarly, for t >= 1: |L_{t+1}| ≤ |L_t| * (k-1) (if t>0) because each vertex in L_t has a parent edge (to previous layer) so remaining degree capacity is k-1 for children. For t=0, capacity k.

    Additionally, note that vertices in the last layer (max distance) have no children, so no capacity needed.

    These inequalities are reminiscent of the condition for existence of a tree where each non-root vertex has at most k children? Actually it's like a rooted tree with maximum degree k (except root can have up to k children, others up to k-1 children). This is similar to constructing a BFS tree respecting degree constraints. However, is it necessary that we use a tree? Could we possibly use non-tree edges to "help" with degree constraints? For example, if some layer has too many vertices to be children of previous layer given capacities, could we add edges between vertices in same layer to "satisfy" the condition that each vertex in L_t (t>0) has a parent? No, the parent must be from previous layer. That condition is absolute. So each vertex in L_t must have at least one neighbor in L_{t-1}. If we add edges between vertices in L_t and L_{t-1} beyond the tree edges, they would be additional children? Actually, they would serve as possible parents. A vertex v in L_t could have multiple neighbors in L_{t-1}. But it only needs at least one. However, the degree constraints affect vertices in L_{t-1}: if we assign v's parent to some u, that uses one child slot for u. If we instead allow v to have two parents (multiple edges? but multiple edges not allowed) we cannot have two edges to different parents because they both count toward degree, but v still needs at least one parent. Could we use edges within L_t to reduce the need for children from previous layer? No, that doesn't provide a path from root of length t, because to get to v with distance t, you must go through a vertex at distance t-1. So v must be adjacent to at least one vertex in L_{t-1}. So each v requires one edge to previous layer. So the number of edges from L_{t-1} to L_t is at least |L_t|. These edges are incident to vertices in L_{t-1} and each contributes to their degree. So the total number of such edges is |L_t|. The maximum total capacity of vertices in L_{t-1} to accommodate such edges is sum over u in L_{t-1} of (k - deg_other(u)). But deg_other(u) includes its own parent edge (if t-1 >0) and any edges we might add. But the minimal deg_other(u) is just 1 if u != root (since it must have a parent). So the maximum number of children edges that can be assigned to L_{t-1} is at most |L_{t-1}| * (k - 1) if t-1>0, or |L_0| * k if t-1=0. However, note that we might reduce deg_other(u) by not giving it a parent? But if u is not root, it must have a parent. So it must have at least one edge to previous layer. So its degree includes at least that edge. Could we instead have u's parent edge be from within same layer? No, because then distance to root would be at most t-2? Actually if u in L_{t-1} and has an edge to some w in L_{t-1}, then w also has distance t-1; that doesn't provide a path to root shorter than t-1, so u still needs a parent in L_{t-2} to achieve distance t-1. So yes, each non-root vertex must have at least one neighbor in previous layer, i.e., at least one parent. So it will have at least one degree consumed by that parent edge. So the maximum number of children it can have is k - 1. Unless we allow u to have no parent? That would contradict u's distance being t-1 (if t-1>0). Because then the shortest path from root to u must be t-1; if it has no neighbor in L_{t-2}, it could still have a neighbor in L_{t-1}? But that wouldn't reduce distance; the distance would be at least t because any path from root must go through some vertex; if all neighbors are either in L_{t-1} or L_t, then the shortest path length could be t (if it has neighbor in L_{t-1}? Actually if it's in L_{t-1} and has a neighbor in L_{t-1}, that neighbor also at distance t-1, then the path to root could be via that neighbor? But that neighbor also needs a parent in L_{t-2} to have distance t-1. So there would be a path root... -> some w in L_{t-2} -> neighbor -> u, length t. So u's distance would be at most t, but if u has no direct neighbor in L_{t-2}, could it still have distance t-1? Let's analyze: Suppose u is at distance t-1. Then there exists a shortest path of length t-1 from root to u. The last edge on that path goes from some vertex v at distance t-2 to u. So u must be adjacent to some vertex in L_{t-2}. So it must have at least one neighbor in L_{t-2}. Therefore, each vertex with distance >0 must have at least one neighbor in the previous layer. So the parent edge is mandatory.

    Thus, the necessary condition is:

    Let cnt[d] be number of vertices with distance d. Let D = max d.

    • cnt[0] = 1.
    • For each d from 1 to D, we must have cnt[d] ≤ cnt[d-1] * (k - (d-1 > 0 ? 1 : 0)? Wait careful: The capacity for children from layer d-1 is: if d-1 == 0, each vertex in layer 0 can have at most k children (since no parent). So total capacity = cnt[0] * k = k (since cnt[0]=1). So we need cnt[1] ≤ k.
    • For d >= 2: each vertex in layer d-1 can have at most k-1 children (because it already has one parent edge). So total capacity = cnt[d-1] * (k-1). So we need cnt[d] ≤ cnt[d-1] * (k-1) for d >= 2.

    These conditions are necessary.

    But are they sufficient? Possibly yes, by constructing a tree where each vertex in layer d-1 gets at most its capacity children. Since we can assign children arbitrarily, we can always do this if the inequality holds. However, we also need to ensure that the degree of each vertex doesn't exceed k; in this tree, root degree = cnt[1] ≤ k, okay; for a vertex in layer d (1 ≤ d < D), degree = 1 (parent) + children. Children assigned should be ≤ k-1. If we assign exactly up to capacity, it's fine. For leaf vertices (d = D) degree = 1 (parent) only, which is ≤ k as long as k ≥ 1 (which is true because k < n and k≥1). So it's okay.

    But wait, what about vertices in intermediate layers that have zero children? That's fine, degree = 1. It's okay even if k=1? Since k < n and k ≥ 1? In constraints, 1 ≤ k < n ≤ 10^5. So k could be 1. In that case, for d>=1, capacity is k-1 = 0. So cnt[d] must be 0 for d>=2. Also cnt[1] ≤ k = 1. So maximum possible is root + possibly one vertex at distance 1, and no further vertices. So tree is just a line of length at most 1. That makes sense: if max degree 1, graph is a matching or path? Actually degree ≤1 means graph is a collection of paths and cycles, but connected forces it to be a path. With root degree ≤1, the only connected graph with max degree 1 is two vertices connected by an edge (or single vertex). So indeed.

    Thus, the tree construction works.

    However, is there any scenario where the necessary inequality fails but a graph could still exist using cross-layer edges (i.e., edges within same layer) to "provide" a parent? No, because the parent must be from previous layer. Edges within same layer don't help for that. So the inequality is necessary.

    But also we need to check that the distance values themselves are consistent. For example, triangle inequality: for any edge we add, it's satisfied automatically if we only add edges between layers differing by at most 1. However, we must also ensure that there are no shorter paths that produce distances smaller than given. If we only add tree edges, distances are exactly depths. But if we add extra edges, could they create shorter paths and thus violate distances? Yes. So we must ensure that any extra edges we add do not create a path from root to a vertex shorter than its d. In a tree, adding any extra edge might create shortcuts. So if we strictly follow a tree, distances are preserved. So the tree is safe.

    Thus, the problem reduces to: given array d, check:

    • There is exactly one d[i] = 0.
    • Let D = max d.
    • Let cnt[t] = number of vertices with distance t.
    • For t = 1: cnt[1] ≤ k.
    • For t ≥ 2: cnt[t] ≤ cnt[t-1] * (k-1).

    If these hold, we can construct a tree by connecting each vertex in layer t (t>0) to a parent in layer t-1 arbitrarily, respecting that each parent gets at most k (if layer 0) or k-1 children.

    We also need to ensure that the total number of edges m is within limit (≤ 10^6). n ≤ 10^5, so a tree has n-1 edges, ≤ 10^5-1 < 10^6, fine.

    But is there any other nuance? The input could have distances that are not contiguous: e.g., some distance value missing? That is allowed? Suppose we have d = [0,2]; missing distance 1. Could that be possible? Let's think: If there's a vertex with distance 2, it must have a neighbor at distance 1. But if there is no vertex with distance 1, that's impossible because the neighbor must exist. So we need that for any t > 0, if cnt[t] > 0 then cnt[t-1] > 0. In other words, distances must form a contiguous set from 0 to D. Otherwise, impossible. Because for vertex with distance t>0, there must be a vertex at distance t-1 (the previous hop). If cnt[t-1]=0, there's no such vertex. So necessary: For all t = 1..D, cnt[t-1] > 0. But since we have cnt[0]=1 and we compute D, this condition reduces to that there are no gaps: i.e., for every t from 1 to D, cnt[t] may be zero? Actually if cnt[t]=0 but cnt[t+1]>0, then vertex with distance t+1 would need a neighbor at distance t, but there is none. So it's impossible. So we must have cnt[t] > 0 for all t from 0 to D? Not necessarily for t between 0 and D, we could have cnt[t] = 0 if there are no vertices at that distance, but then vertices at distance t+1 cannot exist. So if D is max, then for all t < D, cnt[t] must be > 0? Actually consider distances: root distance 0, then there might be vertices at distances 1, 2, 3. Could we have cnt[2] = 0 but cnt[3] > 0? That would mean there is a vertex at distance 3, but there is no vertex at distance 2. However, the shortest path to that vertex goes through some vertex at distance 2 (the second-to-last step). That vertex must exist in the graph. But it might not have distance exactly 2? Wait, the vertex on the path at distance 2 from root must have distance 2 from root. So it would be counted in the array d. So it must be present. So indeed cnt[2] cannot be 0. Therefore, for all distances t from 0 to D, cnt[t] must be at least 1. So distances must be contiguous.

    Thus, we need to check: For each t from 0 to D, cnt[t] > 0. Actually cnt[0] must be 1. For t=1,...,D-1, if any cnt[t] == 0, impossible.

    Now, what about the condition that d[i] < n? That's given.

    Now, also check that the array might contain negative? No.

    So we have necessary and sufficient conditions? Let's test with examples.

    Example 1: n=3, k=2, d=[0,1,1] cnt[0]=1, cnt[1]=2. Check: cnt[1] ≤ k? 2 ≤ 2 ok. Since D=1, only layer 1 needed, condition ok. Construct: root=1 (or whichever has d=0, say vertex 1). Connect root to vertices in layer 1 (2 and 3). But also need to satisfy maximum degree: root degree=2 ≤ k=2. For vertices 2 and 3, degree=1 (parent) ≤ k=2. So tree works. But sample output has three edges: they also added edge between 2 and 3 (same layer). That's extra but not needed. So tree is valid.

    Example 2: n=4, k=2, d=[2,0,1,3] Wait sample input: "4 2" and "2 0 1 3". So d: d1=2, d2=0, d3=1, d4=3. Let's parse: vertex1:2, vertex2:0 (root), vertex3:1, vertex4:3. cnt[0]=1 (vertex2), cnt[1]=1 (vertex3), cnt[2]=1 (vertex1), cnt[3]=1 (vertex4). Check: cnt[1]=1 ≤ k=2 ok. cnt[2]=1 ≤ cnt[1](k-1)=11=1 ok. cnt[3]=1 ≤ cnt[2](k-1)=11=1 ok. All contiguous. Construct tree: root (2) connect to layer1: vertex3. Vertex3 connect to layer2: vertex1. Vertex1 connect to layer3: vertex4. Degrees: root deg=1 ≤2; vertex3 deg=2 (parent + child) ≤2; vertex1 deg=2; vertex4 deg=1. So tree works. Sample output edges: (1 3), (1 4), (2 3). That's different: They connected vertex1 to vertex3 (parent? that would make distance to root: vertex1 (d=2) connecting to vertex3 (d=1) gives path 2-3-2? Actually root=2? Wait d2=0 so root is vertex2. In sample output: edges: 1 3, 1 4, 2 3. So graph: 2-3, 3-1, 1-4. Distances: from root 2: to 2=0; to 3=1; to 1: path 2-3-1 =2; to 4: path 2-3-1-4=3, correct. So tree (2-3, 3-1, 1-4) is exactly the BFS tree described. So they output the tree. They didn't need extra edges.

    Example 3: n=3, k=1, d=[0,0,0]. That has three zeros, impossible because only one zero allowed. Output -1. That matches.

    Thus, the tree construction works.

    But we should consider potential pitfalls: Could there be cases where the tree conditions are satisfied but the actual distances from root in the constructed tree might not equal the given d if there are vertices with same distance that are connected differently? In a tree, distance from root equals depth. So if we assign each vertex a parent from the previous layer, then its depth is exactly d[v] because the parent's depth is d[v]-1, so its depth = (d[v]-1)+1 = d[v]. So all good.

    But we must also ensure that there is no alternative shorter path via cross edges (but we don't add any). So it's fine.

    Now, is there any scenario where the inequalities hold but the tree construction fails because we need to assign parents but the capacity per vertex is not integer? No.

    But we must be careful: The capacity for a vertex in layer t (t>0) is k-1, but that is the maximum number of children it can have. However, if k-1 = 0 and cnt[t] > 0, the only way to satisfy cnt[t] ≤ cnt[t-1]*0 is cnt[t]=0. So that's handled.

    Thus, the algorithm:

    1. Read n, k.
    2. Read array d[1..n].
    3. Check: exactly one d[i] == 0. If not, output -1.
    4. Compute max_d = max(d).
    5. Count cnt[t] for t=0..max_d. Also verify that for each t from 1 to max_d, cnt[t] > 0? Actually if max_d>0, we need that cnt[t] > 0 for all t=1..max_d? Not necessarily; it could be that some intermediate t has 0? But we argued impossible. But we should check: If there exists t such that 1 ≤ t ≤ max_d and cnt[t] == 0, then impossible. Because a vertex with distance t+1 must have a neighbor at distance t, but no vertex at distance t exists. So we should check that for each t from 0 to max_d-1, cnt[t] > 0. Since cnt[0] is 1, that ensures all previous layers exist. Actually we need for each t = 1..max_d, cnt[t-1] > 0. So we can check: for t from 1 to max_d: if cnt[t] > 0 and cnt[t-1] == 0, impossible. But easier: ensure cnt[0] = 1 and that for all t from 1 to max_d, cnt[t] >= 1? Wait if max_d is the maximum distance, then for t = max_d, cnt[t] > 0. For all t < max_d, we cannot guarantee cnt[t] > 0? Suppose we have distances: 0, 2 (max_d=2). Then cnt[1] = 0, cnt[2] > 0. This violates the condition because vertex with distance 2 needs a vertex at distance 1. So impossible. So we need that for all distances t from 0 to max_d, cnt[t] > 0. That is, there are no gaps. So we can compute cnt and then verify that cnt[t] > 0 for all t=0..max_d. Since max_d is the max, it's sufficient.

    But note: There might be distances larger than max_d? No.

    So check: for each t=0..max_d, if cnt[t]==0 -> -1.

    1. Check degree constraints:
      • If cnt[1] > k: impossible. (since root can have at most k children)
      • For t=2..max_d: if cnt[t] > cnt[t-1] * (k-1): impossible.

    Note: For k=1, k-1=0. So for t>=2, cnt[t] must be 0, and also max_d <= 1. This matches.

    If all checks pass, we can construct the graph.

    Construction:

    We need to output edges. We'll produce a tree by connecting each non-root vertex to a parent in the previous layer. We must ensure that each parent's number of children does not exceed capacity: root: at most k; others: at most k-1. Since we've checked the total counts, it's possible to assign. A simple greedy assignment: For each layer t from 1 to max_d, iterate through vertices in layer t, assign each to a parent from layer t-1 that currently has assigned children less than its capacity.

    We'll need to keep track of capacities: For each vertex in layer t-1, capacity = (t-1 == 0 ? k : k-1). Initially each has capacity. As we assign children, decrement capacity. Since total required children = cnt[t] and total capacity = sum of capacities = (if t-1==0) k * cnt[0] else (k-1)*cnt[t-1]. And we've ensured cnt[t] ≤ total capacity, so greedy assignment works.

    We also need to output edges. So we need to know which vertices belong to each layer. We can group vertices by distance.

    Implementation details:

    • Input up to 10^5, so we can store arrays.

    • We'll create vector<vector> layers(max_d+1) where layers[t] contains indices (1-indexed) of vertices with d[i] = t.

    • Validate layers: for t from 0 to max_d, layers[t] not empty. Also exactly one at layer0.

    • capacities: For each vertex we could store remaining capacity. But we can also simply assign by iterating: For layer t, we have parents = layers[t-1]. We'll assign children to parents in a round-robin fashion, ensuring each parent gets at most cap. Since total children ≤ total capacity, we can distribute sequentially.

    Simpler: For each parent vertex, we can compute how many children it should get: We want to fill capacities as evenly as possible? Not necessary; any distribution works as long as each parent doesn't exceed its cap. We can just iterate over children and assign to the next parent that still has capacity. We can keep an index pointer to parent and a count of assigned children per parent.

    But we need to know for each parent its capacity. For root (t-1=0) cap = k; for others cap = k-1.

    We'll maintain for each parent in layer t-1 an integer remaining capacity. Since the total number of parents is at most n (10^5) we can store an array rem_cap for each vertex? But vertices are identified by index. We could create a map or array of size n+1 for capacity, but we only need it for parents in current layer. So we can have an array rem of length n+1 initialized to 0, but we set for vertices in layer t-1: rem[vertex] = (t-1==0 ? k : k-1). Then as we assign children, decrement.

    Alternatively, we can just loop: For each child in layer t, we need to find a parent with remaining capacity. Since total children and parents are O(n), we can maintain a pointer to the current parent index and a count of how many children assigned to that parent. When that parent reaches its capacity, we move to next parent.

    Implementation:

    For t from 1 to max_d: let parents = layers[t-1]; let children = layers[t]; let cap_per_parent = (t-1 == 0) ? k : (k-1); int parent_idx = 0; int assigned_to_current = 0; for each child in children: if assigned_to_current == cap_per_parent: parent_idx++; assigned_to_current = 0; // assert parent_idx < parents.size() because total capacity check ensures enough. output edge: (parents[parent_idx], child) assigned_to_current++;

    But careful: Not all parents may have same capacity? Actually they all have same cap per layer: root: k, others: k-1. So yes, all parents in the same layer have same capacity. So this round-robin distribution will work because we will not exceed total capacity. However, we must ensure that when we move to next parent, we haven't run out of parents. Since total children ≤ total capacity = parents.size() * cap_per_parent, the loop will finish before exhausting parents. The condition parent_idx < parents.size() will hold because we only increment when we've filled current parent and there are still children left; but we must check that when we increment, there is still a next parent. Actually if we fill the last parent exactly and there are no more children, we won't increment beyond. If we fill the last parent and there are still children, that would mean we've used all capacity of all parents, so total children would be > total capacity, contradiction. So safe.

    Edge case: if cap_per_parent = 0? That would happen when k=1 and t-1>0 (i.e., for layers beyond first). But we would have already ensured cnt[t] = 0 for t>=2, so no children to assign. So loop for t from 1 to max_d, but if max_d >=2 and k=1, we would have earlier deemed impossible because cnt[2] would be >0. So no need to handle cap_per_parent=0 because the loop won't run for such t.

    Now, after building edges, we have a tree with n-1 edges. We must output m = number of edges = n-1? Actually we could output exactly these edges. But is it required to output exactly n-1 edges? The problem says m (0 ≤ m ≤ 10^6) — the number of edges in the found graph. So we can output n-1. But careful: If n=1? But constraints: k < n, so n>=2? Actually 1 ≤ k < n ≤ 10^5, so n >=2 because k < n, and k ≥ 1, so n≥2. So n-1 >=1.

    But there is a nuance: The graph must be connected. The tree is connected.

    Thus, solution seems straightforward.

    But we should double-check if any valid distance array that passes these conditions could still be impossible due to other hidden constraints. For example, what about vertices with distance 0 but multiple? We already covered.

    What about distances that are not tree-realizable due to parity or something? In an undirected graph, distances are just lengths. The BFS tree always gives those distances. So as long as we can assign parents, it's fine.

    But is there a scenario where the BFS tree would violate the condition that for any edge (u, v), |d[u]-d[v]| ≤ 1? In our tree, we only assign edges between consecutive layers, so that's satisfied.

    Now, could there be a scenario where the BFS tree constructed as above violates the "at most k edges adjacent to each vertex" because we used exactly children counts within capacity, but we also must consider that the parent edge counts too. In our assignment, we gave each non-root vertex exactly one parent, and we limited children to capacity. So degrees are within k. So fine.

    Thus, the algorithm is:

    • Validate.
    • Build layers.
    • Output edges connecting each non-root vertex to a parent in previous layer with capacity constraints.

    But we must also ensure that we output exactly m edges. Our construction yields exactly n-1 edges (a tree). That's fine.

    But is there any situation where we need to output extra edges? Not needed.

    Now, let's test with some custom cases.

    Case: n=5, k=2, d = [0,1,1,2,2]. cnt[0]=1, cnt[1]=2, cnt[2]=2. Check: cnt[1]≤k =>2≤2 ok. cnt[2]≤cnt[1](k-1)=21=2 ok. Construction: root (v0) has cap 2. Assign two children from layer1: say v1, v2. Then layer1 parents: v1 cap=1, v2 cap=1. Layer2 children: v3,v4 assign: v1 gets one child, v2 gets one child. Degrees: root=2, v1=2, v2=2, leaves=1. Works.

    Case: n=6, k=2, d = [0,1,1,2,2,2]. cnt[0]=1, cnt[1]=2, cnt[2]=3. Check: cnt[2]≤2*1=2? Actually 3 > 2, fails. So impossible. Could there be any graph that satisfies? Let's think: root degree max 2, so can connect at most 2 vertices directly. Those two vertices each can have at most 1 extra edge (since they already have parent) to vertices at distance 2. So total distance-2 vertices ≤ 2. So impossible. Good.

    Case: n=7, k=3, d = [0,1,1,1,2,2,2]. cnt[0]=1, cnt[1]=3, cnt[2]=3. Check: cnt[1]≤3 ok, cnt[2]≤cnt[1](k-1)=32=6 ok. So possible. Construction: root cap 3, assign 3 children. Each of those 3 has cap 2 (k-1=2). Need to assign 3 children among them. One possible: parent1 gets 2, parent2 gets 1, parent3 gets 0. Then degrees: root=3, parent1=1+2=3, parent2=1+1=2, parent3=1+0=1. All ≤3. Works.

    Case: n=6, k=2, d = [0,1,2,3,3,3]. cnt[0]=1, cnt[1]=1, cnt[2]=1, cnt[3]=3. Check: cnt[1]≤2 ok; cnt[2]≤cnt[1](1)=1 ok; cnt[3]≤cnt[2](1)=1? Actually 3 ≤ 1? No, 3 > 1 fails. So impossible. Could we use edges within same layer to help? For distance 3 vertices, they need a parent in layer 2. There is only one vertex in layer 2, which can have at most k-1=1 child (since it already has a parent). So only one vertex in layer 3 can be connected directly to that vertex. But could other distance-3 vertices have parents from layer 2 but also maybe from layer 3? No, parent must be from layer 2. So impossible.

    Case: n=4, k=3, d = [0,0,1,1] -> two zeros, impossible.

    Case: n=4, k=2, d = [0,2,1,3]? Let's check contiguity: we have distances 0,1,2,3 all present? Actually we have 0,2,1,3 -> distances: 0,1,2,3 all present (0 one,1 one,2 one,3 one) => contiguous? Yes, because cnt[0]=1, cnt[1]=1, cnt[2]=1, cnt[3]=1. But note that order: vertex with d=2 must have a parent at distance 1, and vertex with d=3 parent at distance 2. Check capacity: cnt[1]=1 ≤ k=2; cnt[2]=1 ≤ cnt[1](k-1)=11=1; cnt[3]=1 ≤ cnt[2](k-1)=11=1; all ok. So should be possible. Build tree: root (d0) connect to d1 vertex; d1 connect to d2; d2 connect to d3. Degrees: root=1, d1=2, d2=2, d3=1, all ≤2. Works. So array [0,2,1,3] is valid? But note that the array given is per vertex index; it's not sorted. That's fine.

    Now, consider scenario where distances are not strictly BFS-like: Could there be a valid graph that is not a tree, but the distance array passes our conditions, yet the tree construction fails because of capacity? No, if it passes, we can build a tree.

    Thus, the solution seems correct.

    But we must consider the possibility that the source vertex is not the one with d=0? Actually by definition, d[i] is the distance from the chosen vertex to i. So the chosen vertex has d=0. So we can identify it. So the root is the vertex with d=0. So we need to use that as root.

    Now, edge cases: n large, k up to n-1. Our algorithm O(n) grouping and assignment works.

    Now, confirm the constraints on output m: must be ≤ 10^6. n ≤ 10^5, so n-1 ≤ 99,999, safe.

    Now, are there any other constraints like the graph must be simple, no multiple edges, which we adhere.

    Thus, solution outline:

    • Read input.
    • Count zeros. If zeros != 1 -> -1.
    • Determine max_d = max(d_i).
    • Build cnt array for t=0..max_d (use vector of size max_d+1, initialize 0). For each i, cnt[d[i]]++.
    • Check that for every t from 0 to max_d, cnt[t] > 0. If any zero -> -1.
    • Check capacity: if cnt[1] > k -> -1 (but only if max_d >=1, but if max_d==0? then no cnt[1] and condition is vacuously true; but max_d==0 means only root vertex; but n>1? Since k < n, n≥2, so max_d cannot be 0 because there would be other vertices with distance 0? Actually if n≥2, and root only one, other vertices must have distance >0, so max_d ≥ 1. So n≥2, max_d≥1. But we can still check safely: if max_d>=1 then cnt[1] must exist and be >0 due to contiguity, and we check.)
    • For t=2 to max_d: if cnt[t] > cnt[t-1] * (k-1) -> -1.
    • If all checks pass, construct edges.
      • Group vertices by distance: vector<vector> layers(max_d+1).
      • For i from 1 to n: layers[d[i]].push_back(i).
      • The root is layers[0][0] (since only one).
      • We'll store edges in a list.
      • For t = 1 to max_d: parents = layers[t-1]; children = layers[t]; cap = (t-1 == 0) ? k : (k-1); // assign children to parents in round-robin: int p_idx = 0; int assigned_to_cur = 0; for child in children: // ensure we have capacity in current parent // But we need to check if assigned_to_cur reached cap, move to next parent. // Since total children <= total capacity, we won't run out. while (assigned_to_cur == cap) { p_idx++; assigned_to_cur = 0; // p_idx will stay within bounds because total children condition. } output edge (parents[p_idx], child); assigned_to_cur++;
      • After loop, output m = number of edges (should be n-1). Print edges.

    But wait: The assignment algorithm above may not correctly handle when cap=0? It won't be executed because if cap=0, then children list must be empty; else we would have an infinite loop while (assigned_to_cur == 0)?? Actually we start with assigned_to_cur=0; if cap=0, then condition assigned_to_cur == cap (0==0) true, we go into while loop and increment p_idx, assigned_to_cur remains 0, then condition remains true, we will keep incrementing p_idx indefinitely until out of bounds. So need to guard: if cap==0, then children must be empty; we can skip the layer if cnt[t]==0, which is already ensured by contiguity and capacity check. But if k=1 and max_d=1, then for t=1, cap = (t-1==0)? k : k-1 -> cap = k =1, fine. For t=2, we won't have because max_d=1. So safe. But to be robust, we can check if cap == 0 and children not empty -> impossible (should have been caught earlier). In code, we can simply proceed; but to avoid potential infinite loop, we can just assert that if cap==0, then children empty. We could also modify the loop: for child in children: while (assigned_to_cur >= cap) {...} with cap possibly 0, but while (assigned_to_cur >= 0) would be always true. So we need to treat cap==0 specially: it would mean no child can be assigned, so children must be empty. So we can just skip layer if no children. So we can add if (children.empty()) continue; then cap >0? Not necessarily if k=0? But k>=1, and for t-1>0 cap = k-1, which could be 0 if k=1. But if k=1 and t-1>0, then max_d cannot exceed 1 because if t>=2 then children would exist and capacity 0, which would have been caught in capacity check. So by the time we are constructing, we have already ensured that for t>=2, cnt[t] <= cnt[t-1] * (k-1). If k=1, then (k-1)=0, so cnt[t] must be 0. So layers[t] will be empty for t>=2. So the loop for t will only go up to max_d=1. So we won't encounter cap=0. So safe.

    Thus, implementation is fine.

    Now, we need to ensure we output the edges in any order, no specific.

    Let's test with some random valid inputs to ensure the greedy assignment doesn't run out of parents. Suppose cnt[t-1]=2, cap_per_parent=2, total capacity=4, cnt[t]=4. We assign: parent0 gets 2, then assigned_to_cur becomes 2; next child, assigned_to_cur==cap, so p_idx increments to 1, assigned_to_cur=0; then assign to parent1: 1st child assigned_to_cur=1, 2nd child assigned_to_cur=2, then next child? Actually we have 4 children: after parent1 gets second child, assigned_to_cur becomes 2, and we have assigned 4 children total? Let's simulate: children list length=4. Start: p_idx=0, assigned_to_cur=0. Child1: assign to parent0, assigned_to_cur=1. Child2: assign to parent0, assigned_to_cur=2. Child3: while (assigned_to_cur == cap) -> true: p_idx=1, assigned_to_cur=0; then assign to parent1, assigned_to_cur=1. Child4: assign to parent1, assigned_to_cur=2. Done. Works.

    If cnt[t]=3 with same capacities: after child2, assigned_to_cur=2; child3: while condition true? Actually assigned_to_cur == cap (2==2) true, so we go to next parent: p_idx=1, assigned_to_cur=0; then assign to parent1, assigned_to_cur=1. Works.

    If cnt[t]=0, skip.

    Thus, algorithm works.

    Now, we should also consider if the graph we output must satisfy that there is at most k edges adjacent to each vertex. In our tree, root has exactly cnt[1] children; we ensured cnt[1] ≤ k. Others have 1 parent + children; children ≤ k-1, so total ≤ k. So ok.

    But what about vertices in the last layer? They have only parent, so degree 1 ≤ k (k≥1).

    Now, we must also ensure that the graph is undirected and connected. Yes.

    Thus, solution seems complete.

    But wait, the problem statement says "at most k edges adjacent to each of its vertices." So our tree respects that.

    Now, I will consider if there is any scenario where the distance array passes the inequality but still impossible due to something else. For instance, if the distance array has a vertex with d=1 but no neighbor in layer 0? But we connect it to root, so fine.

    Another potential issue: The array d must be consistent with the graph being connected and without multiple edges. But we construct a tree, which is connected and simple.

    Now, think about possibility that the source vertex (with d=0) might have degree more than k if we assign all children to it. But we've checked cnt[1] ≤ k.

    Now, verify with given examples. Example1: n=3,k=2,d=[0,1,1]. Our algorithm: cnt[0]=1, cnt[1]=2, max_d=1. Check: cnt[1]≤2 ok. Build layers: layer0: [1], layer1: [2,3]. cap for root=2. Assign children: both to root. Output edges: 1-2, 1-3. That's a tree. Sample output has 3 edges including 2-3. Both are acceptable.

    Example2: works.

    Example3: fails zeros check.

    Now, I'd like to test with a more complex valid case to ensure greedy assignment does not exceed capacity for a specific parent when parents have varying capacity? But they all have same capacity per layer. So fine.

    Now, we must consider the case where k is large, like n-1. Then the inequalities are easily satisfied. The capacity constraints become: cnt[1] ≤ n-1, always true since cnt[1] ≤ n-1? Actually cnt[1] ≤ n-1, but n-1 ≤ k? k=n-1, so cnt[1] ≤ n-1, ok. For t>=2: cnt[t] ≤ cnt[t-1] * (k-1) = cnt[t-1] * (n-2). Usually this holds for most arrays? Not necessarily, because cnt[t] could be huge relative to cnt[t-1]. But if k is large, the product is large, so likely holds. But still need contiguity. So works.

    Now, consider if there is a scenario where the array d contains zeros for multiple vertices. We treat as -1. That's correct.

    Now, think about negative distances? Not allowed.

    Now, we should also consider the possibility that the graph may have cycles or extra edges, but we output tree, which is valid. So no issues.

    Now, is there any scenario where the array d is such that it's impossible to have a connected graph with max degree ≤ k even if the tree conditions are satisfied? I think not. Because the tree conditions are necessary and sufficient.

    But we must double-check necessity: For a vertex u with distance t, it must have at least one neighbor in layer t-1. So the number of edges between layer t-1 and t is at least cnt[t]. Since each vertex in layer t-1 can be incident to at most (k - (t-1>0?1:0)) such edges (because it already has at least one edge to layer t-2, unless t-1=0). This gives exactly the inequality. So it's necessary.

    Now, sufficiency: we show construction of a tree with exactly those edges.

    Thus, the answer is to output -1 if any condition fails else output a tree.

    Now, there is one more nuance: The graph must be undirected and without multiple edges. Our tree satisfies that.

    Now, ensure that we output m = number of edges (n-1). The problem says "print integer m (0 ≤ m ≤ 10^6) — the number of edges in the found graph." So we must output m first. So we compute m = n-1. But what if n=1? n must be at least 2 due to k<n and k≥1, but just in case? The constraint says 1 ≤ k < n ≤ 10^5, so n≥2. So m≥1. But if n=2 and k=1, distances could be [0,1]? Let's test: n=2, k=1, d = [0,1]. cnt[0]=1, cnt[1]=1, check cnt[1] ≤ k? 1≤1 ok. Build tree: root to other, degree root=1≤1, other=1≤1. Output edge. Works.

    Now, consider n=2, k=1, d = [1,0] similar.

    Now, also consider if d = [0,0]? n=2 but then zeros=2, fails.

    Now, consider if d = [0,2] with n=2? That would be max_d=2, but n=2, distances: root and another with d=2, but there must be vertices at distance 1, so impossible. Our contiguity check fails because cnt[1] = 0 while max_d=2, so -1.

    Now, there is another nuance: The input distances are given as d[i] from 1 to n. The source vertex is unknown but we deduce it's the zero. However, there could be a vertex with distance 0 that is not unique? Already handled.

    Now, the problem statement: "Valera had an undirected connected graph without self-loops and multiple edges consisting of n vertices. The graph had an interesting property: there were at most k edges adjacent to each of its vertices. ... Help him restore the lost graph." It does not require that the graph we output must have exactly the same property? It says "the required graph" meaning a graph that matches the notes and the property. So we must output a graph with max degree ≤ k.

    Thus, our algorithm works.

    Now, check if there is any scenario where the tree construction might violate the degree constraint for some vertex because we assigned children to it that exceed capacity, but we have already ensured total children ≤ total capacity, but our greedy assignment might assign more than capacity to a vertex if we incorrectly handle the last assignments? But we use a while loop to move to next parent when current reaches cap. So it's fine.

    But one must ensure that we don't exceed the number of parents. Since we increment p_idx only when we filled current and we have more children, we might go beyond parents.size()-1 if we incorrectly assume there is another parent. However, the condition for moving to next parent is assigned_to_cur == cap. Suppose we have parents with capacities, but the last parent might be filled exactly, and then there are still children left. Then we will increment p_idx to be equal to parents.size() (since last index is size-1, after increment it becomes size). Then we will try to assign the next child, but we will first check while (assigned_to_cur == cap) which will be true, then we increment p_idx again, and assigned_to_cur reset to 0. This will continue incrementing p_idx without bound if we don't break out. We need to ensure that we never try to assign a child after filling the last parent and still have children; that would mean total capacity insufficient. Since we have checked total capacity, when we fill the last parent, we will have assigned exactly total capacity children. If there are still children left, that means total children > total capacity, contradiction. So we will never have that scenario. But what if we fill the last parent and then there are no more children? Then we exit the loop, and we never attempt to assign further children. So the while condition will only be checked before assigning a child. When we are about to assign the child, we check if current parent is full; if it is and it's the last parent, then we would increment p_idx to parents.size() and reset assigned_to_cur=0. Then we would try to assign the child to parents[p_idx] which is out of bounds. However, we can avoid this by not checking condition before each assignment in a way that ensures we only move to next parent if current parent is full and there are more children to assign. But we need to guarantee that when we move to next parent, there is still a parent available. So we should check that p_idx < parents.size() before assignment. Our loop: for child in children: while (assigned_to_cur == cap): p_idx++; assigned_to_cur = 0; output edge(parents[p_idx], child); assigned_to_cur++;

    If after moving p_idx, it becomes equal to parents.size(), then the next line will access parents[p_idx] out-of-bounds. But this situation would only happen if we attempted to assign a child after filling all parents, i.e., total children > total capacity. Since we have assurance that total children <= total capacity, we need to ensure that our while loop does not increment p_idx beyond last parent when it's exactly full and there are no more children. However, the while condition is checked at the start of each child assignment. Consider the case where we have filled the last parent exactly after assigning the previous child. At that point, assigned_to_cur == cap for that parent. Now we go to next child. The while condition is true, so we increment p_idx (making it equal to parents.size()) and reset assigned_to_cur to 0. Then we attempt to output edge with parents[p_idx], which is invalid. This can happen even if total children exactly equals total capacity? Let's simulate: Suppose we have 2 parents, each cap=2, total capacity=4, children=4. We assign:

    • start: p_idx=0, assigned_to_cur=0. Child1: while false (0==2? no) -> assign to parent0, assigned_to_cur=1. Child2: while false (1==2? no) -> assign to parent0, assigned_to_cur=2. Child3: while (2==2) true: p_idx=1, assigned_to_cur=0. Then assign to parent1, assigned_to_cur=1. Child4: while (1==2? false) -> assign to parent1, assigned_to_cur=2. Done. No issue.

    Now scenario: parents=2, cap=2, children=3 (total capacity 4, but only 3 children). After child2, assigned_to_cur for parent0=2. Child3: while (2==2) true -> p_idx=1, assigned_to_cur=0. Then assign to parent1, assigned_to_cur=1. Done. Works.

    Now scenario: parents=1, cap=2, children=2. After child2, assigned_to_cur=2. If there were a child3, it would attempt while true -> p_idx=1 (out of bounds) -> then assign. But we won't have child3 because children=2.

    So as long as total children ≤ total capacity, the while loop will never cause p_idx to go beyond parents.size()-1 when we actually assign a child? Wait, consider the case where parents have capacities, but we exactly fill the last parent with the last child. After assigning the last child, we exit loop; no further child, so fine. But could the while loop cause increment before assignment when the previous parent was exactly full and we still have children? That's what we handled; it moves to next parent, which exists because total capacity not exceeded.

    Now consider edge case: parents=1, cap=0? We said not happen. So it's safe.

    But what about when the capacity of a parent is 0? Then at start, assigned_to_cur=0, cap=0, so while (0==0) true, we will increment p_idx, assigned_to_cur=0, then again while condition true again (0==0), infinite loop if we don't break out. So as argued, we should not have such case because if cap=0 and children non-empty, total capacity =0, but children>0, contradiction. So to be safe, we could check: if cap == 0: then we must have children.empty(); if not, it's impossible (but we already caught earlier). So we can add an assert or simply skip the layer if children.empty(). Since we already check contiguity and capacity, children will be empty if cap==0.

    But for robustness, we can implement assignment differently: For each parent, we can compute number of children it should have: we can distribute children evenly or using a loop that iterates over parents and assign up to cap. That avoids the while loop pitfall. Simpler: We can do:

    for parent in parents: remaining = cap; // each parent capacity But we need to assign all children. So we can maintain a pointer over children.

    Alternatively, do:

    int child_idx = 0; for each parent in parents: for (int i=0; i < cap && child_idx < children.size(); i++) { output edge(parent, children[child_idx]); child_idx++; }

    But this will assign children to parents in order, but might not assign all children if total capacity > children, which is fine. But we must ensure that after iterating over all parents, we have assigned all children. If not, then capacity insufficient, but we already checked. This approach avoids the while loop issues.

    Let's adopt this approach because it's straightforward and safe.

    Implementation:

    vector<pair<int,int>> edges; for t = 1..max_d: vector& parents = layers[t-1]; vector& children = layers[t]; int cap = (t-1 == 0) ? k : (k-1); int child_idx = 0; for (int parent : parents) { for (int i=0; i < cap && child_idx < children.size(); i++) { edges.emplace_back(parent, children[child_idx]); child_idx++; } if (child_idx == children.size()) break; } // after loop, we must have child_idx == children.size() because capacity condition ensures enough slots. // If not, something is wrong (should not happen).

    This is simple and safe.

    Now, we also need to consider that the vertices we group might not be sorted; but order doesn't matter.

    Now, we also need to output m = edges.size(). That will be n-1 if we assign exactly one parent per child. Because each child gets exactly one edge. Our assignment above assigns exactly one edge per child. Since we iterate over parents and assign up to cap children, we will assign all children because total capacity sufficient. So edges count = total children = n-1. Good.

    Now, double-check the root: when t-1 == 0, cap = k. So we assign up to k children to root. That's fine.

    Now, note: It's possible that some parents may not get any children, which is fine.

    Now, check for t such that cap may be large, but the loop will assign as many as possible.

    Now, need to handle the case where there are multiple vertices in layer0? We already ensured exactly one.

    Now, we should also ensure that the constructed graph does not have multiple edges. Since we assign each child to a single parent, and we never add any other edges, there are no multiple edges. Also, we don't assign edges between same vertex because child and parent are distinct.

    Now, let's test with a case where k=2, layers: root (1 vertex), layer1: 2 vertices, layer2: 4 vertices. Check: cnt[1]=2≤2 ok. cnt[2]=4≤cnt[1](k-1)=21=2? Actually 4 > 2, so impossible. So not such case.

    Now, for k=3, layers: root, layer1:3, layer2:9? Check: cnt[2]≤3*2=6, so 9 >6 fails.

    Now, for k=3, layers: root, layer1:3, layer2:5. Check: 5 ≤6 ok. Construction: assign root children: all 3 children (layer1). Then for layer2: need to assign 5 children to 3 parents each cap=2. Total capacity=6. So we can assign. Using our assignment method: parents list = [v1,v2,v3] from layer1. Loop over parents: parent v1: assign up to 2 children: assign child1, child2. parent v2: assign up to 2: child3, child4. parent v3: assign up to 2: child5. Done. Works.

    Now, consider the order of vertices in layers: we don't care.

    Now, we should also consider that the input distances could be not in increasing order; but our grouping works.

    Now, confirm memory: layers: vector of vectors, total n entries.

    Now, edge list: up to n-1 edges, store as vector of pairs.

    Now, output: first line m, then each edge.

    Now, final step: implement in C++.

    Edge Cases:

    • n=2, k=1, d=[0,1] => works.

    • n=2, k=1, d=[1,0] => works, root = vertex 2.

    • n=2, k=1, d=[0,2] => check: max_d=2, cnt[0]=1, cnt[1]=0? Because distance 1 not present. Since cnt[1]=0 but max_d=2, contiguity fails -> -1.

    • n=3, k=2, d=[0,2,2] => cnt[0]=1, cnt[1]=0, cnt[2]=2. Since cnt[1]=0 but cnt[2]>0, contiguity fails -> -1.

    • n=3, k=2, d=[0,1,2] => cnt[0]=1, cnt[1]=1, cnt[2]=1. Check: cnt[1]≤2 ok; cnt[2]≤cnt[1](k-1)=11=1 ok. Works. Construct: root->v2 (d1), v2->v3. Degrees: root=1, v2=2, v3=1. Works.

    Now, also consider the case where k is large but cnt[1] > k is impossible.

    Now, consider the case where max_d = 0? That would imply all vertices have distance 0, but n>1 -> multiple zeros -> already invalid.

    Now, verify the condition "at most k edges adjacent to each vertex" - in our tree, some vertices might have degree less than k, which is fine.

    Now, time complexity O(n).

    Now, need to be careful with reading input and building layers when max_d might be up to n-1 (since d[i] < n). So vector size max_d+1 up to n.

    Now, we should also consider the possibility that the input has d[i] values that are not possible because they exceed n-1? But constraint says d[i] < n, so ok.

    Now, we need to check for potential overflow when computing cnt[t-1](k-1) if using int, but n ≤ 10^5, k ≤ 10^5, product ≤ 10^10, which fits in 64-bit. Use long long for comparison? In C++, int can be 32-bit, max about 2e9. 10^510^5 = 10^10 > 2^31-1. So we need to use long long for the product to avoid overflow. Actually cnt[t-1] and (k-1) are both up to 10^5, product up to 10^10, which exceeds 32-bit signed int (max 2,147,483,647). So we must use long long (or unsigned long long). Since we just compare inequality, we can compute as long long.

    Alternatively, we can avoid multiplication by doing division: check if cnt[t] > cnt[t-1] && k-1 < ceil(cnt[t]/cnt[t-1]) etc, but simpler: use (long long)cnt[t-1] * (k-1). We'll do that.

    Now, also need to check if k-1 could be negative? k ≥ 1, so k-1 ≥ 0.

    Now, potential nuance: The condition for t>=2 uses k-1. But what if k=0? k is at least 1 per constraints (1 ≤ k). So fine.

    Now, we must also consider that the graph must be connected. Our tree ensures connectivity. However, there is a subtle point: The distances must be the shortest distances from the chosen vertex. In our tree, the distance from root to each vertex is exactly the depth. But is it possible that in our tree, some vertex has a shorter path via a non-tree edge? We aren't adding any, so no. So it's fine.

    Now, let's test some random valid arrays to be sure:

    Suppose n=6, k=2, d: [0,1,1,2,2,3]. cnt[0]=1, cnt[1]=2, cnt[2]=2, cnt[3]=1. Check: cnt[1]≤2 ok. cnt[2]≤21=2 ok. cnt[3]≤21=2? Actually cnt[2]=2, product=2, 1≤2 ok. Construction: layers:0: [r], 1: [a,b], 2:[c,d], 3:[e]. Assign root to a,b. Now assign children from layer2: parents = [a,b], cap=1 each. So assign c to a, d to b. Then layer3: parents = [c,d], cap=1 each. e assign to c (or d). Check degree: a: parent + 1 child =2; b:2; c:1+1=2; d:1+0? Actually if we assign e to c, then d has no child, degree=1. All ≤2. Works.

    Now, output edges: r-a, r-b, a-c, b-d, c-e. That's a tree.

    Now, what about a graph that is not a tree but still satisfies distances? Not needed.

    Thus, solution stands.

    Now, verify with sample 2: d = [2,0,1,3]. max_d=3, cnt[0]=1 (vertex2), cnt[1]=1 (vertex3), cnt[2]=1 (vertex1), cnt[3]=1 (vertex4). Check: cnt[1]≤2 ok, cnt[2]≤11=1 ok, cnt[3]≤11=1 ok. Build layers: 0:[2],1:[3],2:[1],3:[4]. Assign: t=1: parent[2] cap=k=2 -> assign child 3 -> edge 2-3. t=2: parents=[3] cap=k-1=1 -> assign child 1 -> edge 3-1. t=3: parents=[1] cap=1 -> assign child 4 -> edge 1-4. Edges: (2,3),(3,1),(1,4). That's exactly sample output (though order may differ; sample output had (1 3),(1 4),(2 3), which is same edges). Good.

    Now, we should also check that the root is vertex2, but in sample output they list edges: 1 3, 1 4, 2 3. That includes (1,3) which is child of 3? Actually in our tree, 1 is connected to 3. In sample output, 1 is connected to 3 and 4. That's different; they have 1-3 and 1-4, and 2-3. That means vertex1 has degree 2 (edges to 3 and 4), vertex3 has degree 2 (edges to 1 and 2), vertex2 has degree 1, vertex4 has degree 1. In this graph, distances from root 2: to 2=0; to 3=1; to 1: path 2-3-1 =2; to 4: path 2-3-1-4 =3, but there is also edge 1-4? Actually there is edge 1-4, so 2-3-1-4 length 3, which matches d[4]=3. So it's also valid. In our tree, we had 1-4 instead of 3-? Actually our tree: 2-3, 3-1, 1-4. That's same as sample? Sample: edges: (1,3), (1,4), (2,3). That's exactly 2-3, 3-1, 1-4. Yes same edges: (1,3) is same as (3,1), (1,4) is (1,4), (2,3) is (2,3). So it's identical. Good.

    Now, we need to confirm that we didn't miss the possibility that the graph must be "connected" and "without self-loops and multiple edges". Fine.

    Now, additional checks: The graph we output must have at most k edges adjacent to each vertex. Our construction ensures that.

    Now, consider the case where k is 1. Then the necessary conditions become:

    • cnt[0] = 1.
    • cnt[1] ≤ 1.
    • For t>=2, cnt[t] ≤ cnt[t-1] * 0 => cnt[t] = 0. So max_d <=1. Thus, only possible graphs are either single vertex (n=1, but n≥2) or a single edge (n=2) or maybe n=2 with d[1]=0,d[2]=1, or d[1]=1,d[2]=0. So we can construct an edge between root and the other vertex. So works.

    Now, we must ensure that our construction for k=1 works: For t=1, cap = k = 1. So root gets at most 1 child. So fine.

    Now, what about if cnt[1] = 0? That would mean max_d=0, but n≥2 => impossible because other vertices have distance>0? Actually if max_d=0, then all distances are 0, multiple zeros => invalid. So we don't need to handle.

    Now, consider n=2, k=1, d=[0,0] -> zeros=2 -> -1.

    Now, consider n=2, k=1, d=[0,1] -> works.

    Now, let's think about a potential nuance: The distance array d is given, but the source vertex is not identified. Our algorithm picks the zero as root. However, is it guaranteed that the vertex with d=0 is the source? Yes.

    Now, what if there is a vertex with distance 0 and also other vertices with distance 0? Then either Valera made a mistake (impossible) or the graph had multiple vertices at distance 0, which would imply they are the same vertex? Not possible. So -1.

    Now, is there any case where the distances are valid but the constructed tree would have a root with degree 0 (if cnt[1]=0)? That would mean no other vertices, but n>1 -> invalid because cnt[1]=0 means there are vertices with distance >0? Actually if n>1 and max_d=0, all zeros, invalid. So no.

    Now, before constructing, we also need to ensure that the distance values are within range and that max_d < n. It's given d[i] < n, but max_d could be n-1. That's fine.

    Now, also note that the graph is undirected; our edges are undirected.

    Now, we should also consider that the problem says "there were at most k edges adjacent to each of its vertices." In the original graph, that property held. In our output, we must ensure the graph also satisfies that property. We do.

    Now, think about the possibility that the input d might be such that a vertex has distance d, but there is no vertex with distance d-1, which we check with contiguity.

    Now, is there any other hidden condition: The graph must be simple (no multiple edges). Our tree ensures that.

    Now, complexity wise, we output up to 10^5 edges, which is within 10^6.

    Now, final step: Write code.

    Implementation plan:

    • Read n, k.
    • Read d array (1-indexed).
    • Count zeros. If zeros != 1 -> print -1 and return.
    • Find max_d = *max_element.
    • Create vector cnt(max_d+1,0).
    • Fill cnt.
    • Check contiguity: for t=0..max_d, if cnt[t]==0 -> print -1 return.
    • If max_d >=1: if cnt[1] > k -> print -1 return.
    • For t=2..max_d: if cnt[t] > (long long)cnt[t-1] * (k-1) -> print -1 return.
    • Now construct layers: vector<vector> layers(max_d+1); for i=1..n: layers[d[i]].push_back(i);
    • vector<pair<int,int>> edges;
    • For t = 1 to max_d: vector& parents = layers[t-1]; vector& children = layers[t]; int cap = (t-1 == 0) ? k : (k-1); int child_idx = 0; for (int parent : parents) { for (int j = 0; j < cap && child_idx < children.size(); j++) { edges.push_back({parent, children[child_idx]}); child_idx++; } if (child_idx == children.size()) break; } // after loop, child_idx should equal children.size() // if not, something wrong, but we trust condition.
    • Output edges.size()
    • For each edge, print ai bi (order doesn't matter; we can print as stored).

    Edge case: If n=1? Not possible because k < n, so n>=2. But to be safe, we could handle n=1 separately: Then d array has one element, must be 0. Graph has 0 edges. k >=1? k < n => k < 1 impossible since k≥1. So n cannot be 1. So ignore.

    Now, we also need to consider if max_d could be 0? Then there would be only root and other vertices? Actually if max_d=0, then all distances are 0, which would mean multiple zeros, already invalid. So we won't get to construction with max_d=0.

    Thus, code.

    Now, test with sample.

    Now, double-check contiguity: we check for t=0..max_d if cnt[t]==0. However, what if there are distances larger than max_d? No.

    Now, consider invalid case: n=3, k=2, d=[0,2,2]. max_d=2, cnt[0]=1, cnt[1]=0, cnt[2]=2. contiguity fails at t=1 -> -1.

    Now, consider invalid case: n=3, k=2, d=[0,1,3]. max_d=3, cnt[0]=1, cnt[1]=1, cnt[2]=0, cnt[3]=1. contiguity fails at t=2 -> -1.

    Now, consider invalid due to capacity: n=4, k=2, d=[0,1,1,2]. cnt[0]=1, cnt[1]=2, cnt[2]=1. Check: cnt[1]≤2 ok; cnt[2]≤cnt[1](k-1)=21=2, 1≤2 ok. So valid. Construct tree: root->v2,v3; then layer2: need to assign child v4 to one of v2 or v3, each cap=1. Works. So output 3 edges.

    Now, test with n=5, k=2, d=[0,1,1,2,2,?] Actually n=5, d: [0,1,1,2,2] we already did.

    Now, test with n=5, k=2, d=[0,1,2,2,2] -> cnt[0]=1, cnt[1]=1, cnt[2]=3. Check: cnt[2]≤cnt[1]*1=1? 3>1 -> fails. So -1.

    Now, what about n=5, k=3, d=[0,1,2,2,2] -> cnt[2]≤1*2=2? 3>2 -> fails. So -1.

    Now, consider case where cnt[1] is zero but max_d=0? Already covered.

    Now, final check: The problem statement says "at most k edges adjacent to each of its vertices." In our tree, root has cnt[1] edges. That's ≤ k. But if k is large, root could have up to k children. But what about other vertices? Their degree is 1 (parent) + number of children (≤ k-1) ≤ k. So fine.

    Now, could there be a scenario where we need to output edges between vertices of same layer to satisfy degree constraints? No, because adding edges would increase degrees, making it harder to satisfy the cap. So it's not helpful.

    Thus, solution is to construct a BFS tree with maximum out-degree constraints.

    Now, we must also ensure that we don't produce an edge between the same vertex (impossible because parent and child are from different layers or same? Could parent and child be the same vertex? No, because layers differ.

    Now, let's think about potential pitfalls in the assignment loop: We must be careful that the parents vector may be large, and we might assign children to parents that exceed their capacity if we incorrectly allow more than cap per parent. Our inner loop limits to cap. Good.

    Now, check if we ever assign a child to a parent that already has a parent edge? Yes, but we are not tracking that; we only assign children edges. The parent edge for that parent was assigned when processing previous layer. So each parent already has one edge from its parent. That's fine; we just need to ensure we don't exceed total degree. Since we limit children to cap = (k - (parent has parent? 1:0)), i.e., k if root, else k-1. So degree won't exceed k.

    Now, one more nuance: When processing layer t, the parents are vertices in layer t-1. They may have been assigned children from previous step? Actually for t-1>0, these parents themselves have children from layer t? That's what we are assigning now; they have no children yet. So at the moment we assign, they have only the edge to their parent (from previous iteration). So it's safe to assign up to k-1 children.

    But what about parents that are also in later layers? No.

    Now, our algorithm does not reassign children to a parent after it has been used; we assign children sequentially. This might lead to some parents getting many children (up to cap) and some getting few. That's okay.

    Now, what about if some parent in layer t-1 has degree already from within same layer edges? We are not adding any. So it's fine.

    Now, let's consider if there could be a situation where we have to assign parents to children but the root's capacity is exactly cnt[1] and we assign all children to root. That's fine.

    Now, everything looks good.

    Now, implement.

    Potential issues:

    • The grouping of vertices by distance: we need to know indices. The root is layers[0][0]. The root might not be vertex 1. That's fine.

    • In the assignment loop, we use parent variable. When we add edge, we should add pair (parent, child). Since graph is undirected, order doesn't matter.

    Now, after constructing edges, we output m = edges.size() and then edges.

    Now, we should also consider if there is any scenario where edges.size() != n-1 due to some bug. It should be.

    Now, test with a small case manually.

    Case: n=4, k=2, d = [0,1,1,2] (vertices: 1:0,2:1,3:1,4:2). cnt[0]=1, cnt[1]=2, cnt[2]=1. Check ok. Build layers: L0=[1], L1=[2,3], L2=[4]. t=1: parents=[1], cap=2, children=[2,3]. Assign: parent=1, j=0: edge 1-2; j=1: edge 1-3. child_idx becomes 2 (all children assigned). break. t=2: parents=[2,3], cap=1, children=[4]. Loop over parents: parent=2, j=0: edge 2-4, child_idx=1 -> break. So edges: (1,2),(1,3),(2,4). That's a tree, degrees: 1:2, 2:2, 3:1, 4:1, all ≤2. Works.

    Now, check that distances from root 1: to 1=0, to 2=1, to 3=1, to 4: via 2 gives 2, correct.

    Now, what if we had chosen a different ordering of parents: our loop over parents in layer1: for parent in [2,3], but we break after assigning the first parent. That's fine; it gives 2 as parent of 4. Could also have assigned to 3. Both valid.

    Now, consider case where k=3, layers: L0=[r], L1=[a,b,c] (3 children), L2=[d,e,f,g,h,i]? Let's compute: cnt[1]=3, cnt[2]=? must be ≤ cnt[1](k-1)=32=6. Suppose 6 children. Then assignment: t=1: root->a,b,c (three edges). t=2: parents=[a,b,c], cap=2 each. Our loop: for parent a: assign up to 2 children (d,e), parent b: assign up to 2 (f,g), parent c: assign up to 2 (h,i). All assigned. Works.

    Now, if cnt[2]=5, then after parent a assign 2, parent b assign 2, parent c assign 1, fine.

    Now, test with a case where cnt[2] is 0: then t=2 loop skipped because children empty.

    Now, final code.

    Now, but we must also consider that the problem statement might allow multiple answers, and our tree might be valid. The sample output for first example includes an extra edge 2-3, which we don't produce. That's fine; any answer is accepted.

    Now, confirm with second example.

    Now, check if there is any scenario where the distance array is valid but the tree cannot be constructed because the root's degree limit k is satisfied but we need to assign children to root, but root is in layer0 and we have cnt[1] children, which may be equal to k. That's fine.

    Now, potential bug: The root's capacity is k, but we might assign more than k children if we mistakenly use cap = k for root, and cnt[1] ≤ k ensures we don't assign more. In our loop, we assign up to cap children per parent, and we break when children assigned. Since total children = cnt[1] ≤ k, and we have only one parent (root) because cnt[0]=1. So root will get exactly cnt[1] children, which is ≤ k. But our loop: for parent in parents (only root) -> for j from 0 to cap-1 while child_idx < children.size(): it will assign all children because children.size() = cnt[1] ≤ cap. So fine.

    Now, if cnt[0] were >1, that would be invalid; we already check zeros=1 so cnt[0]=1.

    Now, but wait: Could there be a scenario where the root's degree limit is exactly k, and we assign cnt[1] children, but later we might add extra edges to root? We won't. So ok.

    Now, think about the case where max_d is large and we need to store layers. This is O(n).

    Now, we must handle input where the distances are given, but there may be vertices with distance greater than max_d? That's the max.

    Now, finalize.

    Now, let's write code in C++:

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n, k;
        cin >> n >> k;
        vector<int> d(n+1);
        int zero_count = 0;
        int max_d = 0;
        for (int i=1; i<=n; i++) {
            cin >> d[i];
            if (d[i] == 0) zero_count++;
            if (d[i] > max_d) max_d = d[i];
        }
        if (zero_count != 1) {
            cout << -1 << '\n';
            return 0;
        }
        vector<int> cnt(max_d+1, 0);
        for (int i=1; i<=n; i++) {
            cnt[d[i]]++;
        }
        // contiguity
        for (int t=0; t<=max_d; t++) {
            if (cnt[t] == 0) {
                cout << -1 << '\n';
                return 0;
            }
        }
        // degree constraints
        if (max_d >= 1 && cnt[1] > k) {
            cout << -1 << '\n';
            return 0;
        }
        for (int t=2; t<=max_d; t++) {
            if (cnt[t] > (long long)cnt[t-1] * (k-1)) {
                cout << -1 << '\n';
                return 0;
            }
        }
        // build layers
        vector<vector<int>> layers(max_d+1);
        for (int i=1; i<=n; i++) {
            layers[d[i]].push_back(i);
        }
        vector<pair<int,int>> edges;
        for (int t=1; t<=max_d; t++) {
            vector<int>& parents = layers[t-1];
            vector<int>& children = layers[t];
            int cap = (t-1 == 0) ? k : (k-1);
            int child_idx = 0;
            for (int parent : parents) {
                for (int j=0; j < cap && child_idx < (int)children.size(); j++) {
                    edges.emplace_back(parent, children[child_idx]);
                    child_idx++;
                }
                if (child_idx == (int)children.size()) break;
            }
            // sanity: child_idx should equal children.size()
        }
        cout << edges.size() << '\n';
        for (auto& e : edges) {
            cout << e.first << ' ' << e.second << '\n';
        }
        return 0;
    }
    

    Now, double-check sanity: We assume cnt[0] = 1, so parents in first iteration is size 1. Good.

    Now, test with the given examples.

    Example1: Input: 3 2 0 1 1 Our code: zeros=1, max_d=1, cnt[0]=1, cnt[1]=2, contiguity ok. Check cnt[1] ≤ 2 ok. For t=2 none. Build layers: L0=[1], L1=[2,3]. t=1: parents=[1], cap=2, children=[2,3]; assign both -> edges (1,2),(1,3). Output m=2? But sample output had m=3 with an extra edge. But our output has 2 edges, which is also valid? Let's check: Graph with edges (1-2) and (1-3) is connected, degrees: 1 has 2 ≤k=2, vertices 2 and 3 have degree 1 ≤2. Distances from root (vertex 1) are: d[1]=0, d[2]=1, d[3]=1. So it's valid. The problem accepts any graph, so 2 edges should be acceptable. However, the sample output had 3 edges, but they didn't say it's the only answer. So our answer with 2 edges is also correct. But wait, the problem statement says "If there are multiple possible answers, print any of them." So it's fine. However, we need to ensure that the graph we output has m edges, and m can be 0 ≤ m ≤ 10^6. Our output of 2 edges is acceptable. But is there any requirement that the graph must have at most k edges adjacent to each vertex, which we satisfy. So yes.

    But hold on: In the sample output for example 1, they output 3 edges: (1 2), (1 3), (3 2). That graph includes an extra edge (2-3). Both are valid. So our solution is okay.

    However, we must ensure that our graph is connected: With two edges, vertices 2 and 3 are both connected to 1, so it's connected. So fine.

    Thus, our output for example1 would be:

    2 1 2 1 3

    But the sample output is different. That's allowed.

    But sometimes online judges might compare output exactly? No, the problem says print any. So it's fine.

    But we should double-check that the problem doesn't require exactly the same number of edges as some minimum? No.

    Now, test example2 with our code:

    Input: 4 2 2 0 1 3 d: [2,0,1,3] zeros=1 (vertex2). max_d=3. cnt[0]=1, cnt[1]=1, cnt[2]=1, cnt[3]=1. Checks: cnt[1]≤2 ok; cnt[2]≤11=1 ok; cnt[3]≤11=1 ok. Layers: L0=[2], L1=[3], L2=[1], L3=[4]. t=1: parents=[2], cap=2, children=[3] -> edge (2,3) t=2: parents=[3], cap=1, children=[1] -> edge (3,1) t=3: parents=[1], cap=1, children=[4] -> edge (1,4) Edges: (2,3),(3,1),(1,4). That's 3 edges, same as sample output. Good.

    Now, example3: zeros=3 -> -1.

    Now, we should test a more complex case to ensure no bugs.

    Case: n=7, k=2, d = [0,1,1,2,2,2,3]? Let's compute: cnt[0]=1, cnt[1]=2, cnt[2]=3, cnt[3]=1. Check: cnt[1]≤2 ok; cnt[2]≤2*1=2? 3 > 2, fails -> -1. So not valid.

    Case: n=7, k=3, d = [0,1,1,2,2,2,3] cnt: 1,2,3,1. Check: cnt[1]≤3 ok; cnt[2]≤22=4? 3 ≤4 ok; cnt[3]≤32=6? 1 ≤6 ok. So valid. Layers: L0=[r], L1=[a,b], L2=[c,d,e], L3=[f]. t=1: parents=[r], cap=3, children=[a,b] -> edges r-a, r-b. t=2: parents=[a,b], cap=2, children=[c,d,e]. Loop: parent a: assign up to 2 -> c,d; parent b: assign remaining e -> edge b-e. So edges: a-c, a-d, b-e. t=3: parents=[c,d,e], cap=2, children=[f]. Loop: parent c: assign f -> edge c-f. Edges: total = 2+3+1=6 = n-1. Degrees: r=2, a=1(parent)+2 children=3 ≤3; b=1+1=2; c=1+1=2; d=1+0=1? Actually d has parent a, but we didn't assign children to d? d is in L2, but we didn't assign any children from L2? Wait L2 vertices are c,d,e; we assigned children to them only as parents for L3. In L3 we only have f, and we assigned f to c. So d and e have no children. So degree: c=1(parent a)+1(child f)=2; d=1(parent a) only; e=1(parent b) only; f=1(parent c). All ≤3. So valid.

    Now, we should also test when k is large and we have many layers.

    Now, about contiguity check: We check that for every t from 0 to max_d, cnt[t] > 0. But what if there are distances > max_d? No. So fine.

    Now, think about a corner: n=2, k=1, d=[0,1] passes all checks. Our code: zeros=1, max_d=1, cnt[0]=1, cnt[1]=1, contiguity ok, cnt[1]≤1 ok. Layers: L0=[root], L1=[other]. t=1: parents=[root], cap=1, children=[other] -> edge. Output 1 edge. Works.

    Now, n=2, k=1, d=[1,0] works similarly.

    Now, n=2, k=1, d=[0,0] zeros=2 -> -1.

    Now, n=2, k=2, d=[0,1] works, output edge.

    Now, n=2, k=2, d=[0,2] -> max_d=2, cnt[0]=1, cnt[1]=0, cnt[2]=1 -> contiguity fails at t=1 -> -1.

    Now, everything seems consistent.

    Now, consider the possibility that the distance array has a vertex with distance 0 but there are others with distance >0, but also some vertices with distance >0 but no path? Already handled.

    Now, let's think about an alternative scenario: The graph might not be a tree, but we could still construct a tree. Our construction is valid.

    Now, we should ensure that we don't exceed the maximum allowed edges (10^6). n ≤ 10^5, so n-1 ≤ 99999, which is far less than 10^6. So safe.

    Now, edge count output: we set m = edges.size().

    Now, one more nuance: The problem says "The first line contains two space-separated integers n and k (1 ≤ k < n ≤ 105). Number n shows the number of vertices in the original graph. Number k shows that at most k edges were adjacent to each vertex in the original graph." It says "at most k edges were adjacent to each of its vertices." So the original graph had that property, and we must output a graph that also satisfies that property and matches distances. Our graph does.

    Now, finalize.

    Now, we need to consider the possibility that the distance array could have d[i] = 0 for exactly one vertex, but also there could be vertices with distance > max_d? No.

    Now, before finalizing, let's verify the necessity of the contiguity condition more formally: Suppose there is a gap: there exists t such that cnt[t] = 0 but there is some vertex with distance > t. Then for a vertex with distance t+1, its shortest path must go through a vertex with distance t (the penultimate vertex). That vertex must exist. So impossible. So necessary.

    Now, the capacity conditions we derived: For layer t≥1, each vertex in layer t must have at least one neighbor in layer t-1. So number of edges between layers t-1 and t is at least cnt[t]. Each vertex in layer t-1 can have at most (k - (t-1>0 ? 1 : 0)) such edges because it already has at least one edge to layer t-2 (if t-1>0). However, what if a vertex in layer t-1 has no edge to layer t-2? Could that happen? If t-1 > 0, the vertex must have a neighbor in layer t-2 to achieve distance t-1. So it must have at least one edge to layer t-2. So yes, it has at least one such edge. So its capacity for children is at most k-1. So the inequality holds.

    But is it possible for a vertex in layer t-1 to have more than one edge to layer t-2? That would increase its used degree, reducing capacity for children. But we are taking the maximum possible capacity, assuming the vertex uses exactly one edge to previous layer. To achieve the necessary edges, we need to be able to assign children so that each vertex's total degree ≤ k. If we allow some vertices to have more than one connection to previous layer (multiple parents), that would consume more degree and make it harder. So the best-case scenario for accommodating children is to have each vertex use exactly one edge to previous layer. Thus, if even under that optimal assignment we cannot fit the required edges, it's impossible. Conversely, if we can assign with each using exactly one parent edge, we can construct a tree. So sufficiency holds.

    Thus, conditions are both necessary and sufficient.

    Now, we might also need to consider that the root may have degree less than or equal to k, but if cnt[1] is less than or equal to k, we can connect them directly.

    Thus, solution correct.

    Now, finalize code.

    But wait, there is a nuance: The array d[i] shows the shortest distance from the vertex Valera chose to vertex i. But we don't know which vertex he chose. We assume it's the one with d=0. But what if there is no vertex with d=0? Then it's impossible because the source distance to itself is 0. So we need to check that there is at least one zero. The problem statement says 0 ≤ d[i] < n, so d[i] could be all >0? That would mean no vertex has distance 0 to the source, which is impossible because the source's distance to itself is 0. So we also need to ensure at least one zero. Our zero_count check ensures exactly one zero. So if zero_count == 0, also impossible. So check is zero_count != 1, not zero_count != 1? Actually we require exactly one zero. So if zero_count != 1, print -1. That covers zero_count == 0 and zero_count >1.

    Now, also check that d[i] are integers.

    Now, we must consider the possibility that the distance array may contain a value larger than max_d? No.

    Now, let's test with a case where zero_count=0:

    n=2, k=1, d=[1,1] -> zero_count=0 -> -1. Is there a graph? Could there be a source such that distances to both vertices are 1? That would require the source not be either of these vertices, but the graph has only 2 vertices. The source must be one of the vertices, so distance to itself is 0. So impossible. So -1 correct.

    Now, test with n=3, k=2, d=[1,1,1] -> zeros=0 -> -1.

    Now, test with n=3, k=2, d=[0,2,2] -> zeros=1, max_d=2, cnt[0]=1, cnt[1]=0, cnt[2]=2 -> contiguity fails because cnt[1]==0 -> -1.

    Now, all good.

    Now, potential overflow: (long long)cnt[t-1] * (k-1) could be up to 10^5 * 10^5 = 10^10, fits in 64-bit.

    Now, final code.

    But wait, there is a subtlety: In the capacity condition for t>=2, we used (k-1). However, what if k = 1? Then (k-1) = 0. And we check cnt[t] > 0 * cnt[t-1] = 0, so if cnt[t] > 0, it's impossible. That matches. But also, we need to ensure that the root's capacity is k = 1. So cnt[1] ≤ 1. So the only possible non-root vertices are at distance 1, exactly one such vertex. So max_d <=1. Good.

    Now, but what about the case where k = 0? Not allowed.

    Now, also note that in the assignment loop, for t>=2, we set cap = k-1. For k=1, cap = 0. Then the inner for loop: for j=0; j < 0 && ... will not execute. So we would iterate over parents and break after the loop? Actually we go through parents, but the inner loop does nothing because j<0 false. So child_idx remains 0. Then after the loop over parents, we break only if child_idx == children.size(). But since children.size() may be 0 (if cnt[t]==0), it's fine. If children.size() >0, then child_idx will be 0 and not equal children.size(), and we will have processed all parents (maybe) and then exit the outer for loop, but we would not have assigned all children. However, we have already checked that cnt[t] <= cnt[t-1]*(k-1). If k=1, then (k-1)=0, so cnt[t] must be 0. So children.size()==0. So we will not encounter the situation where children non-empty and cap=0. So safe.

    But to be extra safe, we could skip the layer if children.empty(). Our code already does nothing if empty because the outer for loop over t will still run, but children empty, so child_idx initially 0, and after the parent loop, child_idx still 0, but children.size()==0, so the condition child_idx == children.size() is true, but it's fine. Actually we don't have any break condition after the parent loop, but we don't need to check. However, we must ensure that we don't have an infinite loop or something? No.

    But there's a minor issue: The parent loop will iterate over all parents even if children empty, doing nothing, which is okay.

    Now, we should also consider that the assignment loop using for (int parent : parents) will iterate through all parents, even if we have already assigned all children. We break early when child_idx == children.size() to avoid unnecessary iterations. That's fine.

    Now, one more nuance: The graph must be undirected, and we output edges as (parent, child). That's fine.

    Now, we should consider if the problem expects edges to be printed with ai < bi or any order. No.

    Now, I'll produce final answer.

    But wait, I recall that there is a known Codeforces problem "Restore Graph" (CF 404C or something). The solution described matches exactly: BFS tree with degree constraints. The typical solution is as we have.

    However, in some versions, they require that the graph must have exactly m edges? No, they allow any.

    Now, also note that the problem statement says "Valera had an undirected connected graph without self-loops and multiple edges consisting of n vertices. The graph had an interesting property: there were at most k edges adjacent to each of its vertices." So the original graph had that property, but we need to output any graph that satisfies the distances and the property. So we are free to output a graph with possibly fewer edges.

    Now, all good.

    Now, we should run some random tests with brute force for small n to ensure no missed conditions. But as reasoning is solid, we can trust.

    Now, finalize.

    But before final, double-check the case where max_d = 0? Not possible due to n>1 and zero_count=1? Actually if n=1, but n≥2. So ignore.

    Now, I'll write final answer in the "final" channel. ```cpp

    #include <bits/stdc++.h> using namespace std;

    int main() { ios::sync_with_stdio(false); cin.tie(0);

    int n, k;
    cin >> n >> k;
    
    vector<int> d(n + 1);
    int zero_count = 0;
    int max_d = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        if (d[i] == 0) zero_count++;
        if (d[i] > max_d) max_d = d[i];
    }
    
    // Exactly one vertex must have distance 0 (the source)
    if (zero_count != 1) {
        cout << "-1\n";
        return 0;
    }
    
    // Count vertices per distance
    vector<int> cnt(max_d + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cnt[d[i]]++;
    }
    
    // Distances must be contiguous (no gaps)
    for (int t = 0; t <= max_d; ++t) {
        if (cnt[t] == 0) {
            cout << "-1\n";
            return 0;
        }
    }
    
    // Check degree constraints for the BFS tree
    if (max_d >= 1 && cnt[1] > k) {
        cout << "-1\n";
        return 0;
    }
    for (int t = 2; t <= max_d; ++t) {
        if (cnt[t] > (long long)cnt[t - 1] * (k - 1)) {
            cout << "-1\n";
            return 0;
        }
    }
    
    // Group vertices by distance
    vector<vector<int>> layers(max_d + 1);
    for (int i = 1; i <= n; ++i) {
        layers[d[i]].push_back(i);
    }
    
    vector<pair<int, int>> edges;
    
    // Construct the tree layer by layer
    for (int t = 1; t <= max_d; ++t) {
        const vector<int>& parents = layers[t - 1];
        const vector<int>& children = layers[t];
        int cap = (t - 1 == 0) ? k : (k - 1); // max children for a parent
        int child_idx = 0;                     // next child to assign
    
        for (int parent : parents) {
            // Give this parent up to 'cap' children
            for (int j = 0; j < cap && child_idx < (int)children.size(); ++j) {
                edges.emplace_back(parent, children[child_idx]);
                child_idx++;
            }
            if (child_idx == (int)children.size()) break; // all children placed
        }
    }
    
    // Output
    cout << edges.size() << '\n';
    for (auto [u, v] : edges) {
        cout << u << ' ' << v << '\n';
    }
    
    return 0;
    

    }