You guys must have solved lots of problems, but ever wondered how test cases for those problems are created?
In this problem, you have to create test cases for a graph problem.
Given N and M, you have to make an undirected graph containing N nodes and M edges. But this graph should satisfy additional property - For every edge of this graph, one endpoint should have odd degree and other endpoint should have even degree. There should be no self - loops or parallel edges in this graph. It's not necessary for the graph to be connected.
Note that, degree of any node U in the graph is defined as total number of edges having U as one of its endpoint.
INPUT:
First line of input will consist of integer T denoting total number of test cases.
Each test case will consist of two integers N and M denoting total number of nodes and edges required in the graph.
OUTPUT:
For each test case,you have to print M lines if such a graph is possible. Each line should contain two integers denoting the endpoints of edge. If there are many possible solutions, you can print any of them. Print 1 if it's not possible to make such a graph.
CONSTRAINTS:
1≤T≤10
2≤N≤105
1≤M≤105
Note that all the edges in this graph have one endpoint having odd degree and one endpoint having even degree.
For first test case, deg(1)=deg(4)=deg(5)=2 and deg(2)=deg(6)=3.
Graph is not possible for second test case.
