Chef Designed a Network

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/SEPT19/hindi/CHEFK1.pdf), [Bengali](http://www.codechef.com/download/translated/SEPT19/bengali/CHEFK1.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/SEPT19/mandarin/CHEFK1.pdf), [Russian](http://www.codechef.com/download/translated/SEPT19/russian/CHEFK1.pdf), and [Vietnamese](http://www.codechef.com/download/translated/SEPT19/vietnamese/CHEFK1.pdf) as well. Chef is a network engineer at CodeChef. Currently, he has to design a network that connects $N$ computers (numbered $1$ through $N$). The network should consist of these $N$ computers and exactly $M$ cables. Usually, a cable needs to connect two different computers, but Chef is okay with connecting computers to themselves too. Therefore, let's describe a cable by the pair of computers $(u, v)$ it connects, where $1 \le u \le v \le N$. However, for each valid pair of computers $(u, v)$, there must be at most one cable that directly connects this pair of computers. Let's define the *data consumption factor* of a computer as the number of computers which are directly connected to it. In particular, if a computer $v$ is directly connected to itself (by a cable $(v, v)$), it is only counted as connected to itself once. The data consumption factor of the whole network is the maximum of data consumption factors of all computers. In the resulting network, each computer needs to be connected (directly or indirectly) to all other computers, so that they could communicate with each other. Determine whether it is possible to design such a network. If it is possible, find the minimum possible data consumption factor of the resulting network. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first and only line of each test case contains two spaceseparated integers $N$ and $M$. ### Output For each test case, print a single line containing one integer ― the minimum data consumption factor or $1$ if Chef cannot design a required network. ### Constraints  $1 \le T \le 5 \cdot 10^5$  $1 \le N \le 10^6$  $0 \le M \le 10^{15}$ ### Subtasks **Subtask #1 (10 points):**  $1 \le N \le 10$  $0 \le M \le 10^3$ **Subtask #2 (10 points):** $1 \le T \le 10^2$ **Subtask #3 (10 points):** $1 \le T \le 10^3$ **Subtask #4 (70 points):** original constraints ### Example Input ``` 3 2 3 5 6 3 3 ``` ### Example Output ``` 2 2 2 ``` ### Explanation **Example case 1:** The optimal configuration (and the only configuration) of computers is to connect computers $1$ and $2$, connect computer $1$ to itself and computer $2$ to itself. Then, the consumption factor of each computer is $2$ because it is directly connected to itself and the other computer. **Example case 3:** Here, the cables can connect pairs of computers $(1, 2)$, $(1, 3)$ and $(2, 3)$. The consumption factor of each computer is $2$. There is a configuration with consumption factor $1$, where each computer is connected to itself, but all the computers are not connected, so this network configuration is invalid.Author:  admin5 
Editorial  https://discuss.codechef.com/problems/CHEFK1 
Tags  admin5, anand20, cases, constructive, graphtheory, math, sept19 
Date Added:  16082019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 