PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Srikkanth R and Utkarsh Gupta
Tester: Manan Grover
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
Constructive algorithms, Graph
PROBLEM
Given N and M, find a connected undirected simple graph with N nodes and M edges having the maximum number of bridges. If multiple such graphs exist, print any.
A bridge is an edge in a graph such that removing this edge increases the number of connected components in the graph.
EXPLANATION
I’m going to explain a bit of complicated construction. There exist far simpler constructions, but this one I believe would be more instructive. For a simpler solution, refer solutions section.
When M = N-1
We have N nodes and N-1 edges. The required graph is any tree, and each edge of the tree is a bridge. Hence, we get N-1 bridges.
When M = N*(N-1)/2
In this case, an edge exists between each pair of nodes in the given graph. The number of bridges is 0 for N \geq 3 and exactly one bridge for N = 2.
General case
Let’s assume X is the maximum number of bridges. Then there must be X+1 cyclic components in the graph, such that these X edges connect them.
Let’s assume sizes of these components are S_1, S_2 \ldots S_{X+1} where \displaystyle \sum_{i = 1}^{X+1} S_i = N holds.
What is the number of edges you can add to these components? It is \displaystyle \sum_{i = 1}^{X+1} S_i*(S_i-1)/2.
The above quantity is maximized, when we make X components of size one and last components of size N-X. The maximum number of edges we can add is (N-X)*(N-X-1)/2 + X (Added number of edges inside last component and the X bridges.)
So, if M \leq (N-X)*(N-X-1)/2 + X, then we can have at least X bridges. We can find the largest X such that this inequality holds.
Construction
There can be multiple constrictions for this problem. I’d share mine here.
Dividing N nodes into X+1 components, first X components consisting of 1 node each, and last component consisting of N-X nodes. First add edges from i to $N for 1 \leq i \leq X. Then keep adding edges in last component until graph contains M edges.
Note
Although this construction was not the easiest one, this one gives an idea of how mathematical proofs can be applied in graph problems naturally. There’s also a very simple construction (as compared to this), which I have attached below.
TIME COMPLEXITY
SOLUTIONS
Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
ll temp=(i*(i-1))/2;
temp+=(n-i);
if(temp>=m)
{
int cnt=0;
for(int j=i+1;j<=n;j++)
{
cout<<1<<' '<<j<<'\n';
cnt++;
if(cnt==m)
break;
}
for(int j=1;j<=i;j++)
{
for(int k=j+1;k<=i;k++)
{
if(cnt==m)
break;
cout<<j<<' '<<k<<'\n';
cnt++;
}
}
break;
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T=1;
cin>>T;
int t=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
cin>>t;
while(t--){
I n,m;
cin>>n>>m;
V(P(I,I)) ans;
asc(i,0,n-1){
ans.pb({i+1,i+2});
}
m-=n-1;
asc(i,0,n){
if(m==0){
break;
}
dsc(j,0,i-1){
if(m==0){
break;
}
ans.pb({i+1,j+1});
m--;
}
}
asc(i,0,sz(ans)){
cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
}
}
return 0;
}
Editorialist's Model Solution
import java.util.*;
import java.io.*;
class MAXBRIDGE{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), M = ni();
int X = N-1;
while(((N-X)*(long)(N-X-1))/2+X < M)X--;
for(int i = 1; i<= X; i++){
pn(i+" "+N);
M--;
}
for(int i = X+1; i<= N; i++){
for(int j = i+1; j<= N; j++){
if(M > 0){
pn(i+" "+j);
M--;
}
}
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MAXBRIDGE().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Editorialist's Simple Solution
import java.util.*;
import java.io.*;
class MAXBRIDGE{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), M = ni();
for(int i = 2; i<= N; i++)pn(1+" "+i);
M -= N-1;
for(int i = 3; i<= N; i++){
for(int j = 2; j< i && M > 0; j++, M--){
pn(j+" "+i);
}
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MAXBRIDGE().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
