Subtask 1

The first subtask was meant to reward those who solved the problem by hand. When ~M = 1~, the answer is ~2~. When ~2 \le M \le 3~, the answer is ~3~. When ~4 \le M \le 6~, the answer is ~4~. Finally, when ~7 \le M \le 10~, the answer is ~5~.

Time Complexity: ~\mathcal{O}(T)~

Subtask 2

For the second subtask, it can be seen that in order to minimize the number of vertices, we want to create a graph where there is an edge between as many pairs of vertices as possible. It can be shown that a simple, undirected graph with ~N~ vertices has at most ~\frac{N \times (N - 1)}{2}~ edges. Thus, we are looking for the smallest value of ~N~ such that the inequality ~\frac{N \times (N - 1)}{2} \ge M~ holds true. This can easily be done with a linear search. It can be shown that the linear search takes ~\mathcal{O}(\sqrt{M})~ time in the worst case, though a solution with ~\mathcal{O}(M)~ linear search should also pass.

Time Complexity: ~\mathcal{O}(T \times \sqrt{M})~

Subtask 3

For the third subtask, we can either binary search for the answer using the inequality from subtask 2, or we can make the observation that the solution is always one of ~\sqrt{2 \times M} + 1~ or ~\sqrt{2 \times M} + 2~. Depending on implementation, you may need to use long double instead of double to accurately perform floating point operations.

Time Complexity: ~\mathcal{O}(T)~ or ~\mathcal{O}(T \times \log M)~