Sphere Online Judge

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*(N-1)/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*(N-1)/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:2011-10-18
Time limit:2s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:own problem used for CodeSprint - InterviewStreet Contest

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.