BUET Inter-University Programming Contest

Problem E – Enemy At The Gates

Problem

The kingdom of ByteLand is in trouble. The enemies are going to attack ByteLand. The enemies know that ByteLand has exactly N cities and exactly M bidirectional roads and it is possible to go from any city to every other city directly or via other cities. They also know that any pair of cities can be directly connected by at most one road. But they do not have any information about which road connects which two cities.  They are planning to destroy all critical roads of ByteLand. A road is critical if after destroying that road only at least one pair of cities become disconnected. They are very optimistic so they expect to destroy maximum number of critical roads. What is the maximum number of critical roads that can be present in ByteLand according only to the information the enemies have about ByteLand?

Input

The first line of input contains T  which is the number of tests cases. Each case contains two integers N which is the number of cities and M which is the number of roads .

Output

For each test case output one integer the maximum number of critical roads that could be present in ByteLand.

Explanation of Sample Cases

題目描述：

有 m 條邊，n 個點，一個重要道路被設定為如果這條道路消失了，會有點失聯。
問最多有幾條這種邊？

題目解法：

窮舉有多少個邊(重要道路)，而這個邊只連接一個點到 1。
接著剩餘的點，做一個完全圖，把所有邊都用完。
很簡單的一個 greedy 策略

#include <stdio.h>

int main() {
    int testcase;
    long long n, m, i;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lld %lld", &n, &m);
        if(m < n)
            printf("%lld\n", m);
        else {
            for(i = n-1; i >= 0; i--) {
                long long a = n-i;
                if(a*(a-1)/2 >= m-i) {
                    printf("%lld\n", i);
                    break;
                }
            }
        }
    }
    return 0;
}