PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
Basic Geometry, Principle of Mathematical Induction
PROBLEM:
Given a system of N computers and M wires, we need to compute the minimum data consumption factor ( let’s say \beta ) which is defined as \beta = max ( \delta(C_{1}), \delta(C_{2})....,\delta(C_{N})), where \delta denotes the degree of C_{i}th vertex of our computer network. If we cannot create such a network, we should return 1.
 All computers should be connected to each other (directly or indirectly)
 A pair of computer (C_{i}, C_{j}) could be connected at most once.
 Our system should have exactly M wires (edges) and N computer (vertices)
STRATEGY
To be able to return the smallest \beta from a network, we try to make the network in the following way (This way strives to keep \beta at the minimum at every step)
 Connect N1 wires so as to connect all computers. Let’s say computers C_{1}, C_{N} aren’t connected directly. \beta of the system becomes 2 after the end of this step.
 Now we connect 2 computers C_{1}, C_{N} to themselves using 2 more wires. \beta of the system remains 2 after the end of this step.
 Now we connect computers C_{1}, C_{N} followed by self connecting every computer pair (u,u) that hasn’t already been connected. This would require N2 more wires. \beta of the system becomes 3 after the end of this step.
 Now the problem reduces to the problem of optimally drawing diagonals of a polygon.
DRAWING DIAGONALS
Now we need an efficient way (so as to keep \beta minimum) to be able to draw diagonals of a polygon with sides N. Let’s divide our problem in two cases, when N is even and when N is odd.

WHEN N IS EVEN
Let’s see what happens when we draw a diagonal in a polygon. Since a diagonal connects two points, it increases the degree of both points by 1. Here degree or \delta_{i} is defined as the total number of wires attached directly to a computer C_{i}.
In a polygon with even sides, we can make exactly N/2 diagonals while only raising the degree of every vertex by 1. So, after making N/2 diagonals, \beta increases by 1. We keep making these N/2 diagonals until \beta=N, as N is the highest achievable degree of the system. 
WHEN N IS ODD
Now, when N is odd, we can make \lfloor N/2 \rfloor diagonals which will raise the degree of N1 vertices by 1. Now in the next step when we draw diagonals, we have N+1 points, (1 point left from prev step). So this time we can make (N+1 )/2 diagonals which will raise the degree of N+1 vertices by 1. So in total, after processing 2 times, \beta of our system increases by 2.
We repeat this process too until \beta=N.
ALGORITHM:
We can approach the problem with these steps 
 We first should make sure that it is possible to make a network from the given values of N and M. We need a minimum of N1 wires to be able to connect N computers. Also, for N computers, the maximum wires could be obtained from the expression N*(N+1)/2 .
 Now we divide our questions into 2 steps. We first make a base case when N<3 and other when N>=3
 For N=1, we have two possibilities, M=[ 0, 1], here we simply return M as the degree of vertex C_{1}. When N=2, M=[1,3] and we can return \beta as (M + 6)/4.
 Now we follow the optimal strategy stated above to count wires required to
4 A. Make end connections. ( \beta=2 )
4 B. Complete remaining edge and self connect remaining computers. ( \beta=3 )
4 C. Count wires needed to make diagonals. (4<= \beta <= N)
CODE
#include <iostream>
typedef long long lld;
bool inRange(lld N, lld M) {
return (M >= N1) && (M <= (N*(N+1)/2));
}
lld baseCaseResolver(lld N, lld M) {
if (N==1) {
return M;
}
return (M + 6)/4;
}
lld networkSolver(lld N, lld M) {
if (!inRange(N, M)) {
return 1;
}
if (N < 3) {
return baseCaseResolver(N, M);
}
// Self connections at end
if (N1 <= M && M <= N+1) {
return 2;
}
// Complete side and self connections
if (N+2 <= M && M <= 2*N) {
return 3;
}
// Draw diagonals
M = M  (2*N + 1);
if (N%2 == 0) {
return 4 + (2*M)/N;
} else {
lld period = N/2 + (N+1)/2;
lld index = 4 + 2*(M/period);
index += (M%period >= N/2);
return index;
}
}
int main() {
int T;
std::cin >> T;
while (T) {
lld N, M;
std::cin >> N >> M;
std::cout << networkSolver(N, M) << "\n";
}
return 0;
}
TIME COMPLEXITY
Time complexity of the algorithm discussed in this editorial is O(1) per test case.