# Maximise the bridges MAXBRIDGE Solution Codechef

## Maximise the bridges MAXBRIDGE Solution

Chef is given two integers N and M. Please help Chef find any connected undirected graph G consisting of exactly N vertices and M edges, such that the number of bridges in G is maximized (among all graphs with N vertices and M edges). G cannot have self-loops or multiple edges.

If there is more than one connected undirected graph with the maximum number of bridges, you may print any one of them.

Note: A bridge is an edge whose removal increases the number of connected components of the graph.

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• Each testcase consists of a single line of input, containing two integers N,M the number of vertices and edges of the graph you must construct.

Output Format

For each test case, output M lines where the i-th line contains two space-separated integers denoting the i-th edge of the graph G you constructed. The edges may be printed in any order, and for each edge the endpoints may be printed in any order.

Note that G must not contain self-loops or multiple edges, and no other graph on N vertices and M edges can contain strictly more bridges than G.

Constraints

• 1≤T≤103
• 2≤N≤103
• N−1≤M≤min(N⋅(N−1)/2,105)
• Sum of N over all test cases do not exceed 103
• Sum of M over all test cases do not exceed 105

• Subtask 1 (100 points): Original constraints

Sample Input 1

``````3
4 4
5 4
3 3``````

Sample Output 1

``````1 2
2 3
3 4
1 3
1 2
2 3
3 4
4 5
1 2
2 3
3 1``````

Explanation

Test case 1: There is exactly 1 bridge in the graph and it cannot be increased further.

• Test case 2: Since M=N−1 and we are required to output a connected graph, the graph will always be a tree and hence have 4 bridges. Any tree is acceptable here.

• Test case 3: Since M=N⋅(N−1)/2 our only choice is a complete graph, which has 0 bridges.

• ### SOLUTION

Program Python: Maximise the bridges MAXBRIDGE Solution in Python

``````# cook your dish here
for _ in range(int(input())):
a,b=map(int,input().split())
c={a:[]}
for i in range(1,a):
c[i]=[i+1]
print(i,i+1)
b-=1
flg=3
while b>0:
for j in range(1,flg):

if c[j][-1]<flg:
c[j].append(flg)
print(j,flg)
b-=1
if b==0:
break
flg+=1``````

Program C++: Maximise the bridges MAXBRIDGE Solution in C++

``````#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n,m;

cin>>n>>m;

map<int ,int> x;

for(int i=1;i<n;i++){

x[i]=i+1;

cout<<i<<" "<<i+1<<"\n";

m=m-1;

}

int last=3;

while(m>0){

for(int i=1;i<last;i++){

if (x[i]<last){

x.insert (std::pair<int,int>(i,last));

cout<<i<<" "<<last<<"\n";

m=m-1;

if(m==0){

break;

}}}

last=last+1;

}}
return 0;
}``````

Program Java: Maximise the bridges MAXBRIDGE Solution in Java

``````/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{

static Scanner sc = new Scanner(System.in);

static void solutionWithArray() {
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
}

static void solutionWithoutArray() {
int n = sc.nextInt();
int m = sc.nextInt();
for (int  i = 1; i <= n - 1; i++) {
System.out.println(i + " " + (i + 1));
}
m -= (n - 1);
int max = 3;
while (m != 0) {
for (int i = 1; i <= max - 2; i++) {
if (m == 0) {
break;
}
System.out.println(i + " " + max);
m--;
}
max++;
}
}

public static void main (String[] args) throws java.lang.Exception
{
int t = sc.nextInt();
while(t-->0)
{
solutionWithoutArray();
}
}

}``````

## November Long Challenge 2021 Solution

### 2 thoughts on “Maximise the bridges MAXBRIDGE Solution Codechef”

1. bc chutiya samjha he kya , site pe likh rakha he ki solution denge aur madarchod fir solution na dekar poora question firse repeat ka rakha he , ja bsdk gaand mara madarchod.

• 