SPOJ Problem Set (classical)
9749. Cliques
Problem code: CODESPTG

A clique in a graph is set of nodes such that there is an edge between any two distinct nodes in the set. It is well known that finding the largest clique in a graph is a computationally tough problem and no polynomial time algorithm is known for it. However, you wonder what is is the mininum size of the largest clique in any graph with N nodes and M edges. Of course, the graph should have at most one edge between any two nodes and no edges connecting a node to itself.
Input :
The first line contains T the number of test cases. Each of the next T lines contain 2 integers : N, M
Output :
Output T lines, one for each test case, containing the desired answer for the corresponding test case.
Sample Input :
3
3 2
4 6
5 7
Sample Output :
2
4
3
Constraints :
1 <= T <= 100000
2 <= N <= 10000
1 <= M <= N*(N1)/2
Explanation:
For the second test case, the only valid graph having 4 nodes and 6 edges is one where each pair of nodes is connected. So the size of the largest clique cannot be smaller than 4.
For the third test case, it is easy to verify that any graph with 5 nodes and 7 edges will surely have a clique of size 3 or more.
A clique in a graph is set of nodes such that there is an edge between any two distinct nodes in the set. It is well known that finding the largest clique in a graph is a computationally tough problem and no polynomial time algorithm is known for it. However, you wonder what is is the mininum size of the largest clique in any graph with N nodes and M edges. Of course, the graph should have at most one edge between any two nodes and no edges connecting a node to itself.
Input :
The first line contains T the number of test cases. Each of the next T lines contain 2 integers : N, M
Output :
Output T lines, one for each test case, containing the desired answer for the corresponding test case.
Sample Input :
3
3 2
4 6
5 7
Sample Output :
2
4
3
Constraints :
1 <= T <= 100000
2 <= N <= 10000
1 <= M <= N*(N1)/2
Explanation:
For the second test case, the only valid graph having 4 nodes and 6 edges is one where each pair of nodes is connected. So the size of the largest clique cannot be smaller than 4.
For the third test case, it is easy to verify that any graph with 5 nodes and 7 edges will surely have a clique of size 3 or more.
Added by:  Varun Jalan 
Date:  20111018 
Time limit:  0.299s

Source limit:  50000B 
Memory limit:  1536MB 
Cluster: 
Cube (Intel Pentium G860 3GHz)

Languages:  All except: SCM chicken 
Resource:  own problem used for CodeSprint  InterviewStreet Contest 