The constraints mention that the game must have at least ~2~ end nodes, which can always be satisfied (ex: last choice node is connected to two end nodes). We notice that the game can have at most ~N+1~ end nodes (ex: each choice node other than last is connected to another choice node and an end node, and last choice node is again connected to ~2~ end nodes). We firstly check if our input satisfies these conditions. If not, we output -1.

If our input does satisfy these conditions, we can proceed with our construction. This editorial will explain only one such construction.

We can imagine our choice nodes as a line, with each choice node ~i~ where node ~i~ is not the last node. Node ~i~ will be connected to node ~i+1~.

We will connect the last node to ~2~ ending nodes. For each remaining choice node ~i~, if we still need more end nodes, we can add an extra end node to node ~i~, otherwise, we can connect it to node ~i+2~, which will always already exist.

Time Complexity: ~O(N+M)~.

Challenge: What if cycles are allowed?