codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1867.md (20236B)


      1 Source: https://codeforces.com/blog/entry/120353
      2 
      3 Hello everyone! We're very sorry for the delay >_<
      4 
      5 We hope you enjoyed the tasks! Sorry for too tight limits in C so that Java solutions don't pass (actually one of our authors nickname used to be "java." :D), we'll hopefully do a better job next time! Feel free to leave your feedback in the comments.
      6 
      7 [1867A — green_gold_dog, array and permutation](https://codeforces.com/contest/1867/problem/A)
      8 
      9 Author: [green_gold_dog](/profile/green_gold_dog "Grandmaster green_gold_dog")
     10 
     11 **Tutorial**
     12 
     13 Let's subtract $n$ from the minimum number, subtract $n - 1$ from the second minimum, $n - 2$ from the third $\ldots$, and subtract $1$ from the maximum. Then the number of distinct elements will be $n$. Obviously, it is impossible to achieve a better result.
     14 
     15 Let's prove that the number of distinct elements will be equal to $n$. Suppose $c_i = c_j$, then without loss of generality, let's say that $b_i \gt b_j$, then $a_i \leq a_j$, which means $c_i = a_i - b_i$ < $a_j - b_j = c_j$. Contradiction.
     16 
     17 Time Complexity: $O(n \log n)$ per test case.
     18 
     19 **Solution**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 
     24 using namespace std;
     25 
     26 typedef long long ll;
     27 
     28 void solve() {
     29 	ll n;
     30 	cin >> n;
     31 	vector<pair<ll, ll>> arr(n);
     32 	for (ll i = 0; i < n; i++) {
     33 		ll x;
     34 		cin >> x;
     35 		arr[i].first = x;
     36 		arr[i].second = i;
     37 	}
     38 	vector<ll> ans(n);
     39 	sort(arr.begin(), arr.end());
     40 	reverse(arr.begin(),arr.end());
     41 	for (ll i = 0; i < n; i++) {
     42 		ans[arr[i].second] = i + 1;
     43 	}
     44 	for (auto i : ans) {
     45 		cout << i << ' ';
     46 	}
     47 	cout << '\n';
     48 }
     49 
     50 int main() {
     51     ios_base::sync_with_stdio(false);
     52     cin.tie(0);
     53     cout.tie(0);
     54 	ll t = 1;
     55 	cin >> t;
     56 	for (ll i = 0; i < t; i++) {
     57 		solve();
     58 	}
     59 }
     60 ```
     61 
     62 [1867B — XOR Palindromes](https://codeforces.com/contest/1867/problem/B)
     63 
     64 Author: [ace5](/profile/ace5 "International Master ace5")
     65 
     66 **Tutorial**
     67 
     68 Firstly, a string is a palindrome if and only if for any $i$ ($1 \leq i \leq n$) $s_i = s_{n-i+1}$ (because when reversed, $s_i$ becomes $s_{n-i+1}$).
     69 
     70 We can divide the characters into pairs, where each pair consists of $s_i$ and $s_{n-i+1}$. If $s_i = s_{n-i+1}$, then we need to have $l_i = l_{n-i+1}$ in order to obtain equal elements after XOR. Therefore, either $l_i = l_{n-i+1} = 0$ (with $0$ ones) or $l_i = l_{n-i+1} = 1$ (with $2$ ones). If $s_i \neq s_{n-i+1}$, then $l_i \neq l_{n-i+1}$ must hold ($1$ one in any case). Additionally, if $n$ is odd, then $l_{n/2+1}$ can be either $0$ or $1$ (with $0$ or $1$ ones).
     71 
     72 We can iterate over the number of pairs where $l_i = l_{n-i+1}$ will have two ones, as well as whether there will be a one in the center or not. This way, we can obtain all possible numbers of ones in $l$, i.e., all good $i$.
     73 
     74 Time Complexity: $O(n)$ per test case.
     75 
     76 **Solution**
     77 
     78 ```
     79 #include <bits/stdc++.h>
     80 
     81 using namespace std;
     82 
     83 int main()
     84 {
     85     ios_base::sync_with_stdio(false);
     86     cin.tie(0);
     87     int t;
     88     cin >> t;
     89     while(t--)
     90     {
     91         int n;
     92         cin >> n;
     93         string s;
     94         cin >> s;
     95         string t(n+1,'0');
     96         int ans = 0;
     97         int max_1 = 0;
     98         int max_2 = 0;
     99         for(int i = 0;i <= n/2-1;++i)
    100         {
    101             if(s[i] == s[n-i-1])
    102                 max_2++;
    103             else
    104                 ans++;
    105         }
    106         if(n%2 == 1)
    107             max_1++;
    108         for(int j = 0;j <= max_2;++j)
    109         {
    110             for(int k = 0;k <= max_1;++k)
    111             {
    112                 t[ans + j*2 + k] = '1';
    113             }
    114         }
    115         cout << t << "\n";
    116     }
    117 }
    118 ```
    119 
    120 [1867C-Salyg1n and the MEX Game](https://codeforces.com/contest/1867/problem/C)
    121 
    122 Author: [salyg1n](/profile/salyg1n "Master salyg1n")
    123 
    124 **Tutorial**
    125 
    126 The correct strategy for Alice is to add the number $\operatorname{MEX}(S)$ to the set $S$ on the first move, and add the last removed number on the remaining moves.
    127 
    128 Let m = $\operatorname{MEX}(S \cup {\operatorname{MEX}(S)})$, at the start of the game. In other words, m is equal to the second $\operatorname{MEX}$ of the set $S$. $m \geq 1$.
    129 
    130 Notice that after the first move, $\operatorname{MEX}(S) = m$, and no matter what Bob removes, we will return that number to the set, so the result of the game will always be equal to $m$.
    131 
    132 Let's prove that with Bob's optimal play, we cannot achieve a result greater than m.
    133 
    134 Notice that the $\operatorname{MEX}$ of a set is the largest number k such that all numbers from $0$ to $k-1$ inclusive are present in the set.
    135 
    136 Let $p_i$ be the number of numbers from $0$ to $i-1$ inclusive that appear in the set $S$. Then $\operatorname{MEX}(S)$ is equal to the maximum $i$ such that $p_i = i$.
    137 
    138 If Bob removes the number $y$ during his turn, he decreases all values $p_i$ where $i \gt y$ by $1$. So, if $y = \operatorname{min}(S)$, Bob decreases all non-zero values $p_i$ by $1$.
    139 
    140 Alice can increase some values $p_i$ by $1$ during her turn. Therefore, after Alice's first move, $\operatorname{MEX}(S)$ will no longer increase if Bob keeps removing the minimum, because no non-zero values of $p_i$ will increase (Bob decreases them by $1$, and Alice increases them by at most $1$).
    141 
    142 It is obvious that in order to maximize $\operatorname{MEX}(S)$ after the first move, Alice needs to add the number $\operatorname{MEX}(S)$ to the set $S$.
    143 
    144 We have proven that $R \leq m$ and provided a strategy that achieves a result of $m$.
    145 
    146 Time Complexity: $O(n)$ per test case.
    147 
    148 **Solution**
    149 
    150 ```
    151 #include <iostream>
    152 #include <vector>
    153 
    154 using namespace std;
    155 
    156 void solve() {
    157 	int n;
    158 	cin >> n;
    159 	vector<int> s(n);
    160 	for (int i = 0; i < n; ++i)
    161 		cin >> s[i];
    162 	int mex = -1;
    163 	for (int i = 0; i < n; ++i) {
    164 		if (i == 0 && s[i] != 0) {
    165 			mex = 0;
    166 			break;
    167 		}
    168 		if (i > 0 && s[i] != s[i - 1] + 1) {
    169 			mex = s[i - 1] + 1;
    170 			break;
    171 		}
    172 	}
    173 	if (mex == -1)
    174 		mex = s[n - 1] + 1;
    175 	cout << mex << endl;
    176 	int y;
    177 	cin >> y;
    178 	while (y != -1) {
    179 		cout << y << endl;
    180 		cin >> y;
    181 	}
    182 }
    183 
    184 int main() {
    185 	int t;
    186 	cin >> t;
    187 	while (t--)
    188 		solve();
    189 
    190 	return 0;
    191 }
    192 ```
    193 
    194 [1867D-Cyclic Operations](https://codeforces.com/contest/1867/problem/D)
    195 
    196 Author: [ace5](/profile/ace5 "International Master ace5")
    197 
    198 **Tutorial**
    199 
    200 If $k = 1$, then we can change $b_i$ to $i$, so the answer is YES only if $b_i = i$, otherwise the answer is NO.
    201 
    202 Otherwise, let's build an undirected graph with $n$ vertices and edges ($i, b_i$). Any component of this graph will look like a cycle (possibly of size $1$) to each vertex of which a tree is attached (possibly empty).
    203 
    204 **Proof**
    205 
    206 Let's assume that there are $x$ vertices in a component, then there are also $x$ edges in it (since each vertex has exactly one outgoing edge). We can construct a depth-first search (DFS) tree for this component, which will have $x - 1$ edges. Now, when we add the remaining edge ($u, v$), a cycle is formed in the component (formed by the edge ($u, v$) and the path between $u$ and $v$ in the DFS tree). Each vertex will have a tree attached to it, because before adding the edge, we had a tree.
    207 
    208 Now it is claimed that if the cycle in each component has a size exactly $k$, then the answer is YES, otherwise NO.
    209 
    210 **Proof**
    211 
    212 Let's first consider the situation where the size of the cycle in some component is not $k$. Let the cycle contain vertices $v_1, v_2, \cdots, v_x$ in that order. Now let's look at the last operation in which one of the $l_i$ was equal to some element from the cycle. If the size of the cycle is less than $k$, then in the last operation there will be at least one vertex not from the cycle, which means that at least one vertex from the cycle will be replaced by a number that is not the next vertex in the cycle, which is incorrect because each vertex from the cycle should be replaced by the next vertex after it. If the size of the cycle is greater than $k$, then we will have a vertex from the cycle that will be replaced by a vertex that is not the next vertex in the cycle (otherwise we would have used all the vertices of the cycle, and there are more than $k$ of them). Therefore, in any case, there is no valid last operation with vertices from the cycle, so the answer is NO.
    213 
    214 If the size of the cycle in a component is equal to $k$, then we can apply the following algorithm:
    215 
    216 While there is at least one vertex $v$ in the component that is a leaf, we will perform the operation with $l = [v, b_v, b_{b_v}, \cdots]$ (all elements are distinct because we will enter the cycle and it has a size of $k$). After this operation, we will have $a_v = b_v$, and we can remove vertex $v$ (it had only $1$ outgoing edge).
    217 
    218 When only the cycle remains, we can apply the operation for the vertices in the cycle, preserving the order, and then for all vertices in the component, we will have $a_v = b_v$. By doing this for all components, we will get $a = b$, which is what we wanted, so the answer is YES.
    219 
    220 Time Complexity: $O(n)$ per test case.
    221 
    222 **Solution**
    223 
    224 ```
    225 #include <bits/stdc++.h>
    226 
    227 using namespace std;
    228 
    229 int main()
    230 {
    231     ios_base::sync_with_stdio(false);
    232     cin.tie(0);
    233     int t;
    234     cin >> t;
    235     while(t--)
    236     {
    237         int n,k;
    238         cin >> n >> k;
    239         int b[n];
    240         int vis[n];
    241         for(int j = 0;j < n;++j)
    242         {
    243             cin >> b[j];
    244             vis[j] = 0;
    245         }
    246         if(k == 1)
    247         {
    248             int no = 0;
    249             for(int j = 0;j < n;++j)
    250             {
    251                 if(b[j] != j+1)
    252                 {
    253                     no = 1;
    254                 }
    255             }
    256             cout << (no ? "NO\n" : "YES\n");
    257             continue;
    258         }
    259         int num[n];
    260         int no = 0;
    261         int tgr = 1;
    262         for(int j = 0;j < n;++j)
    263         {
    264             if(!vis[j])
    265             {
    266                 int ind = j;
    267                 int cnum = 0;
    268                 while(!vis[ind])
    269                 {
    270                     vis[ind] = tgr;
    271                     num[ind] = cnum++;
    272                     ind = b[ind]-1;
    273                 }
    274                 if(vis[ind] != tgr)
    275                 {
    276                     tgr++;
    277                     continue;
    278                 }
    279                 if(cnum-num[ind] != k)
    280                 {
    281                     no = 1;
    282                     break;
    283                 }
    284                 tgr++;
    285             }
    286         }
    287         cout << (no ? "NO\n" : "YES\n");
    288     }
    289 }
    290 ```
    291 
    292 [1867E1-Salyg1n and Array (simple version)](https://codeforces.com/contest/1867/problem/E1)
    293 
    294 Author: [salyg1n](/profile/salyg1n "Master salyg1n")
    295 
    296 **Tutorial**
    297 
    298 Let's make queries to subarrays starting at positions $1$, $k + 1$, $2k + 1$, $\ldots$ $m \cdot k + 1$, as long as these queries are valid, meaning their right boundary does not exceed $n$. Let's save the $\operatorname{XOR}$ of all the answers to these queries. We will call these queries primary.
    299 
    300 Now, we will shift the last subarray of the query one unit to the right and make a new query, as long as the right boundary does not exceed $n$. We will call these queries secondary. It is claimed that the $\operatorname{XOR}$ of the entire array will be equal to the $\operatorname{XOR}$ of all the queries. Let's prove this.
    301 
    302 Let $i$ be the position at which the first secondary query starts. Notice that after this query, the subarray [$i$; $i + k - 2$] will turn into the subarray [$i + 1$; $i + k - 1$] and reverse. After the next query, the same thing will happen, the subarray will shift one unit to the right and reverse. Therefore, the prefixes of length $k-1$ of each secondary query will be the same, up to the reversal, which does not affect the $\operatorname{XOR}$. Since the number of secondary queries is equal to $n \operatorname{mod} k$, which is an even number, the $\operatorname{XOR}$ of these prefixes will not affect the $\operatorname{XOR}$ of all the secondary queries, which will therefore be equal to the $\operatorname{XOR}$ of the elements [$a_{i + k — 1}$; $a_n$], that is, all the elements that we did not consider in the primary queries.
    303 
    304 The number of primary queries is equal to $\lfloor \frac{n}{k} \rfloor \leq k \leq 50$, since $n \leq k^2 \leq 2500$.
    305 
    306 The number of secondary queries is equal to $n \operatorname{mod} k \lt k \lt = 50$, since $k^2 \leq 2500$.
    307 
    308 The total number of queries does not exceed $100$.
    309 
    310 **Solution**
    311 
    312 ```
    313 #include <iostream>
    314 
    315 using namespace std;
    316 
    317 int ask(int i) {
    318 	cout << "? " << i << endl;
    319 	int x;
    320 	cin >> x;
    321 	return x;
    322 }
    323 
    324 void solve() {
    325 	int n, k;
    326 	cin >> n >> k;
    327 	int res = 0;
    328 	int i;
    329 	for (i = 1; i + k - 1 <= n; i += k)
    330 	    res ^= ask(i);
    331 	for (; i <= n; ++i)
    332 	    res ^= ask(i - k + 1);
    333 	cout << "! " << res << endl;
    334 }
    335 
    336 int main() {
    337 	int t;
    338 	cin >> t;
    339 	while (t--)
    340 		solve();
    341 	return 0;
    342 }
    343 ```
    344 
    345 [1867E2-Salyg1n and Array (hard version)](https://codeforces.com/contest/1867/problem/E2)
    346 
    347 Author: [salyg1n](/profile/salyg1n "Master salyg1n")
    348 
    349 **Tutorial**
    350 
    351 Let's make queries to subarrays starting at positions $1$, $k + 1$, $2k + 1$, $\ldots$ $m \cdot k + 1$, such that the size of the uncovered part is greater than $2 \cdot k$ and not greater than $3 \cdot k$. In other words, $2 \cdot k \lt n - (m + 1) \cdot k \le 3 \cdot k$. Let's keep the $\operatorname{XOR}$ of all the answers to these queries. We will call these queries primary.
    352 
    353 Let the size of the remaining (uncovered) part be $x$ ($2 \cdot k \lt x \le 3 \cdot k$). Let's learn how to solve the problem for an array of size $x$ in three queries.
    354 
    355 If $x = 3 \cdot k$, simply make queries to positions $1$, $k + 1$, $2 \cdot k + 1$.
    356 
    357 Otherwise, let $y = x - k$. Note that $y$ is even, since $x$ and $k$ are even.
    358 
    359 Make queries at positions $1$, $1 + \frac{y}{2}$, $1 + y$.
    360 
    361 Note that after this query, the subarray [$1$; $k - \frac{y}{2}$] will turn into the subarray [$y/2 + 1$; $k$] and reverse. After the next query, the same thing will happen, the subarray will shift one unit to the right and reverse. Therefore, the prefixes of length $k - \frac{y}{2}$ for each query are the same, up to the reversal, which does not affect the $\operatorname{XOR}$. Since the number of queries in the second group is $3$, which is an odd number, the $\operatorname{XOR}$ of these prefixes will be taken into account exactly once in the $\operatorname{XOR}$ of all the queries, which will therefore be equal to the $\operatorname{XOR}$ of the elements.
    362 
    363 The number of primary queries does not exceed $\lfloor \frac{n}{k} \rfloor \leq k \leq 50$, since $n \leq k^2 \leq 2500$.
    364 
    365 The total number of queries does not exceed $53$.
    366 
    367 **Solution**
    368 
    369 ```
    370 #include <iostream>
    371 
    372 using namespace std;
    373 
    374 int ask(int i) {
    375 	cout << "? " << i << endl;
    376 	int x;
    377 	cin >> x;
    378 	return x;
    379 }
    380 
    381 void solve() {
    382 	int n, k;
    383 	cin >> n >> k;
    384 	int res = 0;
    385 	int i;
    386 	for (i = 1; n - i + 1 >= 2 * k; i += k)
    387 		res ^= ask(i);
    388 	if (n - i + 1 == k) {
    389 		res ^= ask(i);
    390 		cout << "! " << res << endl;
    391 		return;
    392 	}
    393 	int y = (n - i + 1 - k) / 2;
    394 	res ^= ask(i);
    395 	res ^= ask(i + y);
    396 	res ^= ask(i + 2 * y);
    397 	cout << "! " << res << endl;
    398 }
    399 
    400 int main() {
    401 	int t;
    402 	cin >> t;
    403 	while (t--)
    404 		solve();
    405 	return 0;
    406 }
    407 ```
    408 
    409 [1867F-Most Different Tree](https://codeforces.com/contest/1867/problem/F)
    410 
    411 Author: [green_gold_dog](/profile/green_gold_dog "Grandmaster green_gold_dog")
    412 
    413 **Tutorial**
    414 
    415 Here we say that the answer for tree $G'$ is the number of subtrees in $P(G')$ that have an isomorphic subtree in $P(G)$.
    416 
    417 Let's find a tree $T$ of minimum size that has no isomorphic tree in $P(G)$. Let the size of tree $T$ be $x$. Then take a chain of size $n - x$, and let the root of $T$ be the kid of the last vertex on the chain. We say that this is the tree $G'$ we were looking for (with the root of $G'$ being the first vertex of the chain). The number of matching subtrees will be at most $x - 1$, since all subtrees of the vertices on the chain and the subtree $T$ itself will not have isomorphic trees in $P(G)$, because $T$ lies entirely in them, and $T$ has no isomorphic tree in $P(G)$. Therefore, the answer is not greater than $n - (n - x) - 1 = x - 1$.
    418 
    419 Let's prove why the answer cannot be less than $x - 1$: suppose there exists a tree $G*$ for which the answer is less than $x - 1$. Let's find a subtree of minimum size whose size is at least $x$ (it always exists, since we can take the entire tree for example). In this subtree, there are at least $x - 1$ other subtrees, whose sizes are less than $x$ (because in the previous step we chose a subtree of minimum size not less than $x$). And since all trees of size less than $x$ have isomorphic trees in $P(G)$ (by definition $T$ is the tree of minimum size that has no isomorphic tree in $P(G)$ and its size is $x$), the number of matching subtrees in tree $G*$ is at least $x - 1$, which is a contradiction.
    420 
    421 Therefore in our case the answer is $x - 1$.
    422 
    423 Now let's solve the second part of the problem — finding $T$. To do this, let's first find all trees of size 1, then of size 2, then 3, 4 and so on until we find a tree that has no isomorphic subtree in $P(G)$. One can see that if we generate all trees of size up to 15 we will definitely find $T$ there. Within each size, let's number the trees in the order in which we've generated them. To find all trees of size $x$ if we are given all trees of size $x - 1$ and smaller, let's say that the sizes of the children of the root of the tree we generate must not decrease, and if the sizes are the same, their positions in the order must not decrease. Then, we can iterate over the first child, then among the smaller and suitable ones, the second child, then the third, and so on until the total size of the tree becomes exactly $x$. This way, we will enumerate all trees of size $x$ in complexity of their total number (since we will not consider any tree twice and will not consider any extra trees). Let's do this until we find a tree that is not in $P(G)$.
    424 
    425 Hashes can be used to compare trees for isomorphism. For more details, read the [blog post](https://codeforces.com/blog/entry/113465)
    426 
    427 Time Complexity: $O(n \log n)$.
    428 
    429 **Solution**
    430 
    431 ```
    432 #include <bits/stdc++.h>
    433 
    434 using namespace std;
    435 
    436 const int MAXSZ = 15;
    437 
    438 void rec(int ns, int last, vector<int>& now, vector<vector<int>>& aint, vector<int>& col, vector<int>& sz, int& ss, int sns) {
    439     if (ss < 0) {
    440         return;
    441     }
    442 	if (ns == 0) {
    443 		col.back()++;
    444 		aint.push_back(now);
    445 		ss -= sns;
    446 		return;
    447 	}
    448 	for (int i = min(last, col[ns] - 1); i >= 0; i--) {
    449 		now.push_back(i);
    450 		rec(ns - sz[i], i, now, aint, col, sz, ss, sns);
    451 		now.pop_back();
    452 	}
    453 }
    454 
    455 void dfs(int v, int p, vector<vector<int>>& arr, vector<int>& num, map<vector<int>, int>& m, vector<int>& sz) {
    456 	vector<int> now;
    457 	sz[v] = 1;
    458 	for (auto i : arr[v]) {
    459 		if (i != p) {
    460 			dfs(i, v, arr, num, m, sz);
    461 			sz[v] += sz[i];
    462 			if (sz[v] <= MAXSZ) {
    463 			    now.push_back(num[i]);
    464 			}
    465 		}
    466 	}
    467 	if (sz[v] > MAXSZ) {
    468 		num[v] = -1;
    469 		return;
    470 	}
    471 	stable_sort(now.begin(), now.end());
    472 	reverse(now.begin(), now.end());
    473 	num[v] = m[now] - 1;
    474 }
    475 
    476 void dfs2(int x, int p, vector<vector<int>>& aint, vector<int>& ans) {
    477 	if (p >= 0) {
    478 		ans.push_back(p);
    479 	}
    480 	int now = ans.size();
    481 	for (auto i : aint[x]) {
    482 		dfs2(i, now, aint, ans);
    483 	}
    484 }
    485 
    486 void solve() {
    487 	int n;
    488 	cin >> n;
    489 	vector<vector<int>> aint(1);
    490 	vector<vector<int>> arr(n);
    491 	for (int i = 1; i < n; i++) {
    492 		int a, b;
    493 		cin >> a >> b;
    494 		a--;
    495 		b--;
    496 		arr[a].push_back(b);
    497 		arr[b].push_back(a);
    498 	}
    499 	map<vector<int>, int> m;
    500 	vector<int> col(1, 0), sz(1, 1);
    501 	col.push_back(1);
    502 	for (int i = 2; i <= MAXSZ; i++) {
    503 		vector<int> now;
    504 		col.push_back(col.back());
    505 		int ss = n;
    506 		rec(i - 1, aint.size() - 1, now, aint, col, sz, ss, i);
    507 		while (sz.size() < col.back()) {
    508 			sz.push_back(i);
    509 		}
    510 		if (ss < 0) {
    511 		    break;
    512 		}
    513 	}
    514 	for (int i = 0; i < col.back(); i++) {
    515 		m[aint[i]] = i + 1;
    516 	}
    517 	vector<int> num(n), szi(n, 1);
    518 	dfs(0, 0, arr, num, m, szi);
    519 	set<int> s;
    520 	for (int i = 0; i < col.back(); i++) {
    521 		s.insert(i);
    522 	}
    523 	for (auto i : num) {
    524 		s.erase(i);
    525 	}
    526 	int x = *s.begin();
    527 	vector<int> ans;
    528 	if (sz[x] > n) {
    529 		for (int i = 0; i < n; i++) {
    530 			for (auto j : arr[i]) {
    531 				if (i < j) {
    532 					cout << i + 1 << ' ' << j + 1 << '\n';
    533 				}
    534 			}
    535 		}
    536 		return;
    537 	}
    538 	for (int i = 0; i < n - sz[x] - 1; i++) {
    539 		ans.push_back(i);
    540 	}
    541 	dfs2(x, n - sz[x] - 1, aint, ans);
    542 	for (int i = 0; i < ans.size(); i++) {
    543 		cout << ans[i] + 1 << ' ' << i + 2 << '\n';
    544 	}
    545 }
    546 
    547 int main() {
    548     	ios_base::sync_with_stdio(false);
    549     	cin.tie(0);
    550     	cout.tie(0);
    551 	int t = 1;
    552 	//cin >> t;
    553 	for (int i = 0; i < t; i++) {
    554 		solve();
    555 	}
    556 }
    557 ```