search

Google-Developer-Student-Club-CCOEW / Competitive-Coding

7 stars 52 forks source link

Question 72 #156

Closed Mahi1901 closed 2 years ago

Mahi1901 commented 2 years ago

You are given two integers NN and MM. Find any connected undirected graph GG consisting of exactly NN vertices and MM edges, such that the number of bridges in GG is maximized (among all graphs with NN vertices and MM edges). GG 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 TT, denoting the number of test cases. The description of TT 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 MM lines where the i-th line contains two space-separated integers denoting the i-th edge of the graph GG you constructed. The edges may be printed in any order, and for each edge the endpoints may be printed in any order.

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

Constraints 1≤T≤10^3 2≤N≤10^3 N−1≤M≤min(N⋅(N−1)/2,10^5) Sum of NN over all test cases do not exceed 10^3 Sum of MM over all test cases do not exceed 10^5

Sample 1: Input 3 4 4 5 4 3 3 Output 1 2 2 3 3 4 1 3 1 2 2 3 3 4 4 5 1 2 2 3 3 1

AnnadaD commented 2 years ago

Annada Dash Cummins college of engineering for women, Pune Dept: Computer Engineering I would like to work on this issue. Can you please assign me this issue

NikitaMiraje commented 2 years ago

Nikita Miraje Cummins college of engineering for women Dept: Electronics and telecommunication I would like to work on this issue. Can you please assign me this issue?

ManasiGDeshmukh commented 2 years ago

Manasi Deshmukh Cummins college of engineering for women Dept: Computer Engineering I would like to work on this issue. Can you please assign me this issue? @Mahi1901

ShrutikaK2911 commented 2 years ago

Shrutika Kaperavenollu CCOEW IT I would like to work on this issue. Can you please assign me this issue?

Mahi1901 commented 2 years ago

I have assigned. Happy coding!

aditi3004 commented 2 years ago

HEY!!! This is Aditi Sharma(SY-C) MKSSS's CCOEW Computer Engineering

I want to work on this issue Can you assign this to me?