{"trustable":false,"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":"E-Hack DSU! \n\u003cp\u003eAs we all know, disjoint set union is a useful tool. However, sometimes we must apply the strategy of \u003cspan class\u003d\"tex-font-style-it\"\u003eunion by rank\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-it\"\u003epath compression\u003c/span\u003e to make it quick. In general, if we have $$$n$$$ operations of \u003cspan class\u003d\"tex-font-style-it\"\u003emerge\u003c/span\u003e, we may do all these operations in time complexity of $$$O(n \\alpha(n))$$$, where $$$\\alpha(n) \\leq 4$$$ for $$$n \\leq 10^5$$$.\u003c/p\u003e\n\u003cp\u003eLittle Y is the teaching assistant of \u003cspan class\u003d\"tex-font-style-it\"\u003eData Structure\u003c/span\u003e class. One day, one problem was left for practice. There are $$$n$$$ sets numbered from $$$1$$$ to $$$n$$$. Then there are $$$n$$$ pairs of integer $$$(A_i,B_i)$$$. We should merge set $$$A$$$ and $$$B$$$ for each pair $$$(A,B)$$$. The task is to get the count of disjoint sets after all operations.\u003c/p\u003e\n\u003cp\u003eWhen reading the homework codes from students, Little Y noticed one implementation of \u003cspan class\u003d\"tex-font-style-it\"\u003efind\u003c/span\u003e operation without recursion. Then she thinks this code is not implemented correctly, which may lead to about $$$O(n^2)$$$ times of read or write operations to the array $$$\\texttt{parent}$$$. To verify this, she adds a temporary variable called $$$\\texttt{counter}$$$ to track the count of write operations.\u003c/p\u003e\n\u003cpre class\u003d\"lstlisting\"\u003e\u003ccode class\u003d\"prettyprint\"\u003e#include \u0026lt;iostream\u0026gt;\u003cbr\u003eusing namespace std;\u003cbr\u003econst int MAXN \u003d 1e5+10;\u003cbr\u003eint parent[MAXN];\u003cbr\u003elong long counter \u003d 0;\u003cbr\u003e\u003cbr\u003eint find(int x) {\u003cbr\u003e while (x !\u003d parent[x]) {\u003cbr\u003e if (x \u0026lt; parent[x]) {\u003cbr\u003e // Merge-by-rank and Path-compression\u003cbr\u003e parent[x] \u003d parent[parent[x]];\u003cbr\u003e }\u003cbr\u003e x \u003d parent[x];\u003cbr\u003e counter++;\u003cbr\u003e }\u003cbr\u003e\u003cbr\u003e return x;\u003cbr\u003e}\u003cbr\u003e\u003cbr\u003evoid merge(int a, int b) {\u003cbr\u003e a \u003d find(a);\u003cbr\u003e b \u003d find(b);\u003cbr\u003e parent[a] \u003d b;\u003cbr\u003e}\u003cbr\u003e\u003cbr\u003eint main() {\u003cbr\u003e int n, A, B, ans \u003d 0;\u003cbr\u003e cin \u0026gt;\u0026gt; n;\u003cbr\u003e\u003cbr\u003e for (int i \u003d 1; i \u0026lt;\u003d n; i++)\u003cbr\u003e parent[i] \u003d i;\u003cbr\u003e\u003cbr\u003e for (int i \u003d 1; i \u0026lt;\u003d n; i++) {\u003cbr\u003e cin \u0026gt;\u0026gt; A \u0026gt;\u0026gt; B;\u003cbr\u003e merge(A, B);\u003cbr\u003e }\u003cbr\u003e\u003cbr\u003e for (int i \u003d 1; i \u0026lt;\u003d n; i++)\u003cbr\u003e if (i \u003d\u003d find(i))\u003cbr\u003e ans++;\u003cbr\u003e\u003cbr\u003e cout \u0026lt;\u0026lt; ans \u0026lt;\u0026lt; endl;\u003cbr\u003e return 0;\u003cbr\u003e}\u003cbr\u003e\u003c/code\u003e\u003c/pre\u003e\n\u003cp\u003eLittle Y thinks there exists one input data that makes the $$$\\texttt{counter}$$$ large enough. Can you help her to provide one input data to prove that she is right?\u003c/p\u003e\n\u003cp\u003eFor a given $$$n$$$, you should construct $$$n$$$ pairs of integers $$$(A_i, B_i)$$$. When the number $$$n$$$ and $$$n$$$ pairs of integers $$$(A_i, B_i)$$$ is sent to this program, you should guarantee that the final value of $$$\\texttt{counter}$$$ should be greater than a certain number $$$T$$$, which means that this program cannot stop within $$$T$$$ write operations.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eOne line contains two integer $$$n ~ (10 \\leq n \\leq 10^4)$$$ and $$$T ~ (n \\leq T \\leq \\frac{n^2}{\\log_2 n})$$$ denoting the count of initial sets and the least write operations that this program must take.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput $$$n$$$ lines.\u003c/p\u003e\n\u003cp\u003eThe $$$i$$$-th line contains two integers $$$A_i, B_i ~ (1 \\leq A_i, B_i \\leq n)$$$ denoting the $$$i$$$-th pair of number.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e10 10\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \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\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe $$$\\texttt{counter}$$$ of sample input is $$$18$$$.\u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/811e54413c06181624fb8103637917ae?v\u003d1636189374\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"113px\"\u003e \n\u003c/center\u003e"}}]}