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?
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 .
For
each test case output one integer the maximum number of critical roads that
could be present in ByteLand.
Sample Input |
Output for Sample Input |
2 4 4 4 3 |
1 3 |
|
|
Problemsetter:
|
Tasnim
Imran Sunny |
Special Thanks:
|
Shahriar Rouf Nafi
|