In summary, this problem asks us to construct a directed graph of ~N~ nodes with ~M~ edges, such that there are ~X~ SCC's (Strongly Connected Components) on the condition that ~Q~ pairs ~(x_i, y_i)~ belong to the same SCC.

Consider the edge types for a graph with ~X~ SCCs:

• Edges within an SCC. For an SCC consisting of ~\alpha~ nodes (size ~\alpha~), there are a maximum of ~\alpha(\alpha-1)~ possible edges that can be formed.

• Edges between SCCs. Consider all ~\binom{X}{2}~ pairs of SCCs. For an SCC with size ~\alpha~ and another with size ~\beta~, ~\alpha\beta~ edges can be formed between them.

The next step involves choosing ~X~ distinct SCCs:

Subtask 1

Since ~Q = 0~, we pick the ~X~ SCCs to to be ~\{1\}, \{2\}, \dots, \{X-1\}, \{X \dots N\}~. The size of the last SCC needs to be maximized, to maximize the number of edges that can be placed on the first condition listed above.

Subtask 2

Let ~P~ be the maximum number of SCCs that can be created from the input. This can be finding the number of connected components of the ~Q~ constraints with a DSU. If ~P < X~, output -1. If ~P > X~, the largest ~P-X+1~ components (by size) must be considered as 1 SCC, to total ~X~ SCCs. The "largest" are being considered to maximize the number of edges to be placed on the first condition listed above.

Let ~sz[i]~ be the size of the ~i~-th SCC. For the ~X~ SCCs considered, each requires a minimum of ~sz[i]~ edges to satisfy the properties of an SCC, unless it is a single node. For example, if one set of nodes were ~\{1, 2, \dots, k\}~, the edges formed would be ~1 \to 2, 2 \to 3, \dots, k-1 \to k, k \to 1~.

If ~\sum sz[i] > M~, there are not enough edges to satisfy the constraint of ~M~ edges, so output -1.

Finally if ~\sum sz[i] < M~, for each SCC with size ~sz[i]~ you can add ~sz[i](sz[i]-1) - sz[i]~ more edges, and add edges between SCCs. Note that when constructing edges between SCCs, for each pair of SCCs (suppose SCC ~a~ and SCC ~b~), edges must only flow from a node in ~a~ to a node in ~b~, or vice versa. Accounting for both directions will unite ~a~ and ~b~ as 1 SCC, which needs to be avoided.

At this point, if we have already reached our ~M~ required edges, we can simply output them and terminate our program. If ~M~ is still greater than the number of possible edges that can be added, output -1.

Time Complexity: ~\mathcal{O}(N + Q \log N + M \log M)~