Let be the number of edges from vertex to a vertex with a larger index, and let be the number of edges from a vertex with a smaller index to vertex . Then .
Set and . When moving from to , the edges whose left endpoint is become newly included, while the edges whose right endpoint is are removed. Hence and we can uniquely recover from left to right by
For every , we must have and . If any condition fails, print .
Now process the vertices from to . For every previously processed vertex, maintain how many edges it still has to create toward vertices with larger indices. When processing vertex , exactly previous vertices must be connected to .
Choose the vertices with the largest remaining values. Store in a max-priority queue. Each time a pair with vertex is popped, add edge to the answer, decrease its remaining value by , and insert it again. After choosing vertices, insert . If there are too few vertices or the largest remaining value is , the construction is impossible. After processing all vertices, also verify that every remaining value is .
If the process succeeds, the recorded edges form a valid graph, so print the number of edges and the edge list.
Proof
Consider any feasible graph in which the current vertex is connected to a previous vertex but not to another previous vertex . Suppose their current remaining values satisfy .
Let be the number of printed edges. There are priority-queue operations, so the time complexity is . Storing the constructed edges uses space in the worst case.
After using the edge to , vertex still uses edges to later vertices, while uses such edges. Therefore, there must be some vertex such that is an edge and is not. Otherwise every later neighbor of would also be a later neighbor of , implying , a contradiction.
We can delete and and add and . This preserves every degree and every required number of left/right edges. Thus, whenever a feasible solution exists, there is also a feasible solution that prefers a vertex with a larger remaining value at the current step.
Repeating this exchange shows that choosing the largest remaining values at every step preserves feasibility. Therefore, if the priority-queue algorithm fails, no valid graph exists. Conversely, if it succeeds, the edges recorded by the algorithm satisfy every requirement and therefore form a valid graph.
Solution written by GPT5.6