ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5731: p趣味图（specail oj）

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：9 通过：7
提交提交记录统计Web Board

题目描述

    如果满足以下条件，我们称n个顶点的无向图为p趣味图:

        图中正好包含2n+p条边;

        图不包含自循环和重边;

        对于任意整数k(1≤k≤n)，由k个顶点组成的任意子图最多包含2k+p条边。

    图的子图是图顶点的集合和图边的集合。此时，边集必须满足以下条件:集合中每条边的两端必须属于所选的顶点集。

你的任务是找到一个包含n个顶点的p趣味图。

Let's call an undirected graph of n vertices p-interesting, if the following conditions fulfill:
  • the graph contains exactly 2n+p edges;
  • the graph doesn't contain self-loops and multiple edges;
  • for any integer k (1≤k≤n), any subgraph consisting of k vertices contains at most 2k+p edges.
A subgraph of a graph is some set of the graph vertices and some set of the graph edges. At that, the set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices.
Your task is to find a p-interesting graph consisting of n vertices.
Input
The first line contains a single integer t (1≤t≤5) − the number of tests in the input. Next t lines each contains two space-separated integers: n, p (5≤n≤24; p≥0) − the number of vertices in the graph and the interest value for the appropriate test.
It is guaranteed that the required graph exists.
Output
For each of the t tests print 2n+p lines containing the description of the edges of a p-interesting graph: the i-th line must contain two space-separated integers ai,bi (1≤ai,bi≤n;ai≠bi) − two vertices, connected by an edge in the resulting graph. Consider the graph vertices numbered with integers from 1 to n.
Print the answers to the tests in the order the tests occur in the input. If there are multiple solutions, you can print any of them.
Examples
Input 
1
6 0
Output 
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6

输入格式

第一行包含单个整数t(1≤t≤5)表示t组测试数据。接下来的每一行都包含两个以空格分隔的整数:n, p(5≤n≤24;p≥0)−图中的顶点数和相应测试的兴趣值。

保证所需的图是存在的。

输出格式

对于每一个t检验，输出2n+p条包含p-兴趣图的边描述的线:第i条线必须包含两个由空格分隔的整数ai,bi(1≤ai,bi≤n;ai≠bi)−两个顶点，在结果图中由一条边连接。考虑用从1到n的整数编号的图顶点。

按照测试在输入中出现的顺序打印测试的答案。如果有多个解，您可以打印其中任何一个。

样例


Input 
1
6 0
Output 
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6


输入样例 复制 

1
6 0

输出样例 复制 

1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6

分类标签