{"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\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\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\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\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\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\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\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":"Examples","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\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe $$$\\texttt{counter}$$$ of sample input is $$$18$$$.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/811e54413c06181624fb8103637917ae?v\u003d1726229891\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"113px\"\u003e \u003c/center\u003e"}}]}