Chef is given 2 integers N and M. Please facilitate cook realize any connected purposeless graph G consisting of precisely N vertices and M edges, specified the quantity 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's quite one connected purposeless graph with the utmost range of bridges, you will print anyone of them.
Note: A bridge is a grip whose removal will increase the quantity of connected parts of the graph.
Input Format
The first line of input contains one whole number T, denoting the quantity of take a look at cases. the outline of T take a look at cases follows.
Each testcase consists of one line of input, containing 2 integers N,M - the quantity of vertices and edges of the graph you need to construct.
Output Format
For each action at law, output M lines wherever the i-th line contains 2 space-separated integers denoting the i-th fringe of the graph G you created. the perimeters could also be written in any order, and for every edge the endpoints could also be written in any order.
Note that G should not contain self-loops or multiple edges, and no alternative graph on N vertices and M edges will contain strictly a lot of bridges than G.
Constraints
1≤T≤103
2≤N≤103
N−1≤M≤min(N⋅(N−1)/2,105)
Sum of N over all take a look at cases don't exceed 103
Sum of M over all take a look at cases don't exceed a hundred and five
Subtasks
Subtask one (100 points): Original constraints
Sample Input one
3
4 4
5 4
3 3
Sample Output one
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 one: there's precisely 1 bridge within the graph and it can not be enlarged additional.
Test case 2: Since M=N−1 and that we ar needed to output a connected graph, the graph can invariably be a tree and therefore have four bridges. Any tree is appropriate here.
Test case 3: Since M=N⋅(N−1)/2 our solely alternative may be a complete graph, that has zero bridges.
Code: click
ConversionConversion EmoticonEmoticon