U563716 树论

给定一张大小为 $n$ 的完全图，点的编号为 $1\sim n$，点 $i$ 与点 $j$ 之间有一条权值为 $\frac{\mathrm{f}(i,j)+\mathrm{f}(j,i)}{2}$ 的无向边，其中： $$\mathrm{f}(i,j)=\left\{\begin{matrix}\frac{i\times \mathrm{f}(j,i\ \mathrm{mod}\ j)}{i\ \mathrm{mod}\ j} & i\ \mathrm{mod}\ j≠0\\\frac{i}{j} &i\ \mathrm{mod}\ j=0 \end{matrix}\right.$$ 求这张图的最小生成树。

一行一个正整数 $n$，表示图的大小。

第一行输出一个实数，表示这张图的最小生成树的边权和，四舍五入到整数。 之后 $n-1$ 行，每行输出两个以空格隔开的正整数 $u,v$，表示最小生成树的一条边的两个端点（本题使用 Special Judge，用户并不需要关心输出顺序）。

| 测试点编号 | $n≤$ | | :----------: | :----------: | | $1\sim 2$ | $10$ | | $3\sim 5$ | $300$ | | $6\sim 7$ | $5000$ | | $8\sim 9$ | $100000$ | | $10$ | $3000000$ | 对于所有数据，满足 $2≤n≤3\times 10^6$。 若你只答对了最小生成树的边权和，则你可以得到 $40\%$ 的分数。注意，即使你不知道最小生成树的形态，你也需要输出任意一棵树，否则会出现不可预知的错误。