{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e众所周知,不相交集合并是一个很有用的工具。然而,有时我们必须应用“按秩合并”或“路径压缩”策略使其更快。通常情况下,如果我们有$$$n$$$个\u003cspan class\u003d\"tex-font-style-it\"\u003e合并\u003c/span\u003e操作,我们可以在时间复杂度为$$$O(n \\alpha(n))$$$内完成所有这些操作,其中$$$\\alpha(n) \\leq 4$$$为$$$n \\leq 10^5$$$。\u003c/p\u003e\u003cp\u003e小Y是《数据结构》课程的助教。一天,留了一个问题让大家练习。有$$$n$$$个从$$$1$$$到$$$n$$$编号的集合。然后有$$$n$$$对整数$$$(A_i,B_i)$$$。我们应该对每对$$$(A,B)$$$合并集合$$$A$$$和$$$B$$$。任务是在所有操作完成后得到不相交集合的数量。\u003c/p\u003e\u003cp\u003e在阅读学生的作业代码时,小Y注意到了一个没有递归的\u003cspan class\u003d\"tex-font-style-it\"\u003e查找\u003c/span\u003e操作的实现。然后她认为这段代码实现不正确,可能导致对数组$$$\\texttt{parent}$$$进行约$$$O(n^2)$$$次读取或写入操作。为了验证这一点,她添加了一个临时变量叫做$$$\\texttt{counter}$$$来跟踪写入操作的计数。\u003c/p\u003e\u003cpre class\u003d\"lstlisting\"\u003e\u003ccode class\u003d\"prettyprint\"\u003e#include \u0026lt;iostream\u0026gt;\nusing namespace std;\nconst int MAXN \u003d 1e5+10;\nint parent[MAXN];\nlong long counter \u003d 0;\n\nint find(int x) {\n while (x !\u003d parent[x]) {\n if (x \u0026lt; parent[x]) {\n // Merge-by-rank and Path-compression\n parent[x] \u003d parent[parent[x]];\n }\n x \u003d parent[x];\n counter++;\n }\n\n return x;\n}\n\nvoid merge(int a, int b) {\n a \u003d find(a);\n b \u003d find(b);\n parent[a] \u003d b;\n}\n\nint main() {\n int n, A, B, ans \u003d 0;\n cin \u0026gt;\u0026gt; n;\n\n for (int i \u003d 1; i \u0026lt;\u003d n; i++)\n parent[i] \u003d i;\n\n for (int i \u003d 1; i \u0026lt;\u003d n; i++) {\n cin \u0026gt;\u0026gt; A \u0026gt;\u0026gt; B;\n merge(A, B);\n }\n\n for (int i \u003d 1; i \u0026lt;\u003d n; i++)\n if (i \u003d\u003d find(i))\n ans++;\n\n cout \u0026lt;\u0026lt; ans \u0026lt;\u0026lt; endl;\n return 0;\n}\n\u003c/code\u003e\u003c/pre\u003e\u003cp\u003e小Y认为存在一组输入数据使得$$$\\texttt{counter}$$$足够大。你能帮助她提供一组输入数据证明她是对的吗?\u003c/p\u003e\u003cp\u003e对于给定的$$$n$$$,你应该构造$$$n$$$对整数$$$(A_i, B_i)$$$。当数对$$$n$$$和$$$n$$$对整数$$$(A_i, B_i)$$$被发送到这个程序时,你应该保证$$$\\texttt{counter}$$$的最终值应该大于某个数$$$T$$$,这意味着这个程序不能在$$$T$$$次写入操作内停止。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e一行包含两个整数$$$n ~ (10 \\leq n \\leq 10^4)$$$和$$$T ~ (n \\leq T \\leq \\frac{n^2}{\\log_2 n})$$$,表示初始集合的数量和此程序必须执行的最少写入操作次数。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出$$$n$$$行。\u003c/p\u003e\u003cp\u003e第$$$i$$$行包含两个整数$$$A_i, B_i ~ (1 \\leq A_i, B_i \\leq n)$$$,表示第$$$i$$$对数字。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n9 10\n10 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e示例输入的$$$\\texttt{counter}$$$是$$$18$$$。\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/811e54413c06181624fb8103637917ae?v\u003d1708391847\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"113px\"\u003e \u003c/center\u003e"}}]}