Problem of the day
Input: ‘N’ = 5 , ‘M’ = 4 , 'CONNECTIONS' = [[0,1],[1,2],[2,3],[0,3]]
Output: 1
Explanation:
Remove the road between buildings 0 and 3, and add a road between buildings 0 and 4 , or 1 and 4 ,or 2 and 4 or 3 and 4.
The first line of the input contains an integer,’ T’ , denoting the number of test cases.
The first line of each test case contains two integers, 'N’ and ‘M’, denoting the number of buildings and number of connections..
The next ‘M’ lines of each test case contains pair of two integers, denoting the road between buildings.
Return an integer, denoting the minimum changes Sam needs to perform in the blueprint.
1 <= T <= 10
1 <= N <= 100000
1 <= M <= min(N x (N-1)/2 , 100000)
CONNECTIONS[i].length == 2
0 <= Ai,Bi < N
Ai != Bi
There are no repeated connections.
No two buildings are connected by more than one road.
Time Limit: 1 sec
2
5 4
0 1
1 2
2 3
0 2
4 2
0 1
0 3
1
-1
Test 1:
Remove road between buildings 0 and 3, and add a road between building 0 and 4 , or 1 and 4 ,or 2 and 4 or 3 and 4.
Test 2:
There are not enough roads to connect all the building in the city, so return -1.
2
3 2
0 1
1 2
5 4
0 1
1 2
3 4
0 2
0
1