#P18606. Least Annoying Constructive Problem
Least Annoying Constructive Problem
Least Annoying Constructive Problem
有一个n个顶点的完全图。请把它的全部n(n-1)/2条边排成一个圆圈,使得圆圈上任意连续n-1条边组成一棵覆盖全部n个顶点的树。
可以证明,每个合法n都有解。存在多个答案时,输出任意一个即可。这里的树是具有n个顶点、n-1条边的连通无向图。
输入格式
仅一行,一个整数n,3<=n<=500。
输出格式
输出N=n(n-1)/2行,第i行两个整数ui、vi,满足1<=ui<vi<=n。全部边必须互不相同。
把输出行号按模N循环理解。对每个起点i,边i、i+1、...、i+n-2都必须组成一棵树;跨越输出末尾再接回第一行的窗口同样需要满足条件。
样例输入 1
3
样例输出 1
1 2
2 3
1 3
样例输入 2
4
样例输出 2
1 2
3 4
2 3
1 4
1 3
2 4