Suppose we're given a graph with $$$N$$$ vertices and $$$M \space (\le \frac{N \times (N - 1)}{2})$$$ undirected edges, vertices are labelled from $$$0$$$ to $$$N - 1$$$.

We've to add $$$K \space (\le \frac{N \times (N - 1)}{2} - M)$$$ random undirected edges to this graph such that no edge is repeated (including the ones we added).

Goal is to deterministically minimize the number of calls made to $$$rand()$$$ function, only $$$K$$$ calls ideally, choice of edges should be provably random, while keeping rest of the algorithm not too inefficient, for $$$N, M, K \le 10^6$$$.

I feel this problem can be called "pick K random elements without repetition from complement set" where $$${ (i, j) \mid 0 \leq i \leq N \text{ and } 0 \leq j \leq N }$$$ is the universal set and we have a set of $$$M$$$ pairs initially.

I am unable to think any provably random and efficient ways to accomplish this, for example I could pick a random vertex, then pick $$$rand(0, N - degree)$$$ and do some mapping for second vertex, which is $$$O(degree)$$$ probably and can become inefficient.

I would like to know any ideas to accomplish this, thanks.