题目描述

给定一个正整数 $n$，你需要用“分治+递归”的思路，从区间 $[1,\,n]$ 开始，递归地打印出所有区间。具体流程如下：

1. 定义一个函数 dfs(l, r)：

   • 若 $l == r$，只打印一行：“l r”，并返回。
   • 否则，先打印当前区间：“l r”；
   • 然后计算 mid = (l + r) / 2（向下取整），分别递归调用 dfs(l, mid) 和 dfs(mid+1, r)。

从根区间 dfs(1, n) 开始，就可打印所有划分过程中遇到的区间。

请按上述顺序，一行一个区间，输出所有被访问到的区间。

输入格式

n

• 第一行一个正整数 $n$（$1 \le n \le 100,000$）。

由于输出行数最多是所有递归节点数，约为 $2n-1$，此处 $n \le 10^5$ 可以正常输出不超时。

输出格式

请按照“先根节点区间，再递归左子区间，最后递归右子区间”的顺序，每行输出两个整数，表示当前被访问到的区间的左右端点：

l r

5

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

解释：

• 首先打印根区间 [1,5]，

• 计算 mid = 3，于是递归左子区间 dfs(1,3)：

  • 打印 [1,3]

  • mid = 2 → dfs(1,2)：

    • 打印 [1,2]
    • mid = 1 → dfs(1,1) 打印 [1,1]；dfs(2,2) 打印 [2,2]

  • 接着 dfs(3,3) 打印 [3,3]

• 然后回到根的右子区间 dfs(4,5)：

  • 打印 [4,5]
  • mid = 4 → dfs(4,4)；dfs(5,5)