#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