codeforces-scrape

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

1543.md (40389B)


      1 Source: https://codeforces.com/blog/entry/92582
      2 
      3 #### [A: Exciting Bets](https://codeforces.com/contest/1543/problem/A)
      4 
      5 **Hint 1**
      6 
      7 $GCD(a,b)=GCD(a-b,b)$ if $a \gt b$
      8 
      9 **Hint 2**
     10 
     11 $a-b$ does not change by applying any operation. However, $b$ can be changed arbitrarily.
     12 
     13 **Tutorial**
     14 
     15 If $a=b$, the fans can get an infinite amount of excitement, and we can achieve this by applying the first operation infinite times.
     16 
     17 Otherwise, the maximum excitement the fans can get is $g=\lvert a-b\rvert$ and the minimum number of moves required to achieve it is $min(a\bmod g,g-a\bmod g)$.
     18 
     19 **Proof**
     20 
     21 Without loss of generality, assume $a \gt b$ otherwise we can swap $a$ and $b$. We know that $GCD(a,b) = GCD(a-b,b)$. Notice that no matter how many times we apply any operation, the value of $a-b$ does not change. We can arbitrarily change the value of $b$ to a multiple of $a-b$ by applying the operations. In this way, we can achieve a $GCD$ equal to $a-b$. Now, since $GCD(x,y)\leq min(x,y)$ for any positive $x$ and $y$, $GCD(a-b,b)$ can never exceed $a-b$. So, we cannot achieve a higher GCD by any means.
     22 
     23 To achieve the required $GCD$, we need to make $b$ a multiple of $g=a-b$ using as few operations as possible. There are two ways to do so $-$ decrease $b$ to the largest multiple of $g$ less than or equal to $b$ or increase $b$ to the smallest multiple of $g$ greater than $b$. The number of operations required to do so are $b\bmod g$ and $g-b\bmod g$ respectively. We will obviously choose the minimum of the two. Also notice that $a\bmod g=b\bmod g$ since $a=b+g$. So, it doesn't matter if we use either $a$ or $b$ to determine the minimum number of operations.
     24 
     25 **Time Complexity**
     26 
     27 $\mathcal{O}(1)$ per test case.
     28 
     29 **Solution**
     30 
     31 ```
     32 #include <bits/stdc++.h>
     33 using namespace std;
     34 
     35 int main()
     36 {
     37     ios_base::sync_with_stdio(false);
     38     cin.tie(NULL);
     39     int t;
     40     cin >> t;
     41     while(t--)
     42     {
     43         long long a,b;
     44         cin >> a >> b;
     45         if(a==b)
     46             cout << 0 << " " << 0 << '\n';
     47         else
     48         {
     49             long long g = abs(a-b);
     50             long long m = min(a%g,g-a%g);
     51             cout << g << " " << m << '\n';
     52         }
     53     }
     54 }
     55 ```
     56 
     57 #### [B: Customising the Track](https://codeforces.com/contest/1543/problem/B)
     58 
     59 **Hint**
     60 
     61 In the optimal arrangement, the number of cars will be distributed as evenly as possible.
     62 
     63 **Tutorial**
     64 
     65 In the optimal arrangement, the number of traffic cars will be distributed as evenly as possible, *i.e.*, $\lvert a_i-a_j\rvert\leq 1$ for each valid $(i,j)$.
     66 
     67 **Proof (Warning: Too much Math inside)**
     68 
     69 Let's sort the array in non-decreasing order. Let $a_1=p$, $a_n=q$, $p\leq q-2$, $x$ elements of the array be equal to $p$, $y$ elements of the array be equal to $q$, $\displaystyle\sum\limits_{i=x+1}^{n-y}\sum\limits_{j=i+1}^{n-y} a_j-a_i=r$ and $\displaystyle\sum\limits_{i=x+1}^{n-y} a_i=s$.
     70 
     71 The inconvenience of the track will be equal to $S_1=r+x\cdot[s-(n-x-y)\cdot p]+y\cdot[(n-x-y)\cdot q-s]+[xy\cdot(q-p)]$
     72 
     73 Suppose we increase $a_1$ by $1$ and decrease $a_n$ by $1$. Then, the number of occurrences of $p$ and $q$ will reduce by $1$, two new elements $p+1$ and $q-1$ will be formed, and $r$ and $s$ will remain unchanged. In such a case, the new inconvenience of the track will be $S_2=r+(x-1)\cdot[s-(n-x-y)\cdot p]$ $+(y-1)\cdot[(n-x-y)\cdot q-s]$ $+[(x-1)\cdot(y-1)\cdot(q-p)]$ $+[s-(n-x-y)\cdot(p+1)]$ $+[(n-x-y)\cdot(q-1)-s]$ $+[(y-1)\cdot(q-p-1)]$ $+[(x-1)\cdot(q-p-1)]$ $+(x-1)+(y-1)+(q-p-2)$
     74 
     75 Change in inconvenience, $\Delta = S_1-S_2 = [s-(n-x-y)\cdot p]+[(n-x-y)\cdot q-s]+[(x+y-1)\cdot(q-p)]$ $-[s-(n-x-y)\cdot(p+1)]$ $-[(n-x-y)\cdot (q-1)-s]$ $-[(y-1)\cdot(q-p-1)]$ $-[(x-1)\cdot(q-p-1)]$ $-(x-1)-(y-1)-(q-p-2)$ $=2\cdot(n-x-y)+(x+y-1)\cdot(q-p)-(x+y-2)\cdot(q-p-1)-(x-1)-(y-1)-(q-p-2)$ $=2\cdot(n-x-y)+(q-p)+(x+y-1)-1-(x-1)-(y-1)-(q-p-2)$ $=2\cdot(n-x-y+1) \gt 0$ as $x+y\leq n$.
     76 
     77 So, it follows that if $p\leq q-2$. it is always beneficial to move a traffic car from the sub-track with the highest number of traffic cars to the sub-track with the lowest number of traffic cars. If $p=q-1$, applying this operation won't change the inconvenience as this will only swap the last and the first element of the array leaving everything else unchanged. If $p=q$, all the elements of the array are already equal, meaning that we have $0$ inconvenience which is the minimum possible. So, there is no point in applying any operation.
     78 
     79 Now that we have constructed the optimal arrangement of traffic cars, let's find out the value of minimum inconvenience of this optimal arrangement. Finding it naively in $\mathcal{O}(n^2)$ will time out.
     80 
     81 Notice that in the optimal arrangement we will have some (say $x$) elements equal to some number $p+1$ and the other $(n-x)$ elements equal to $p$. Let the sum of all elements in $a$ be $sum$. Then, $x=sum\bmod n$ and $p=\bigg\lfloor\dfrac{sum}{n}\bigg\rfloor$. For each pair $(p,p+1)$, we will get an absolute difference of $1$ and for all other pairs, we will get an absolute difference of $0$. Number of such pairs with difference $1$ is equal to $x\cdot(n-x)$. So, the minimum inconvenience we can achieve is equal to $x\cdot(n-x)$. That's all we need to find out!
     82 
     83 **Time Complexity**
     84 
     85 $\mathcal{O}(n)$
     86 
     87 **Solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 using namespace std;
     92 
     93 int main()
     94 {
     95     ios_base::sync_with_stdio(false);
     96     cin.tie(NULL);
     97     int t;
     98     cin >> t;
     99     while(t--)
    100     {
    101         int n;
    102         cin >> n;
    103         int a[n];
    104         long long s=0;
    105         for(int i=0;i<n;i++)
    106         {
    107             cin >> a[i];
    108             s+=a[i];
    109         }
    110         long long k = s%n;
    111         long long ans = k*(n-k);
    112         cout << ans << '\n';
    113     }
    114 }
    115 ```
    116 
    117 #### [C: Need for Pink Slips](https://codeforces.com/contest/1543/problem/C)
    118 
    119 **Hint 1**
    120 
    121 Did you notice that $v\geq 0.1$?
    122 
    123 **Hint 2**
    124 
    125 The probability of drawing a pink slip can never decrease.
    126 
    127 **Hint 3**
    128 
    129 What would be the complexity of a bruteforce solution?
    130 
    131 **Hint 4**
    132 
    133 Make sure to account for precision errors while comparing floating point numbers.
    134 
    135 **Tutorial**
    136 
    137 Bruteforce over all the possible drawing sequences until we are sure to get a pink slip, *i.e.*, until the probability of drawing a pink slip becomes $1$.
    138 
    139 **Why this works?**
    140 
    141 Whenever we draw a reward other than a pink slip,
    142 
    143 * If $a\leq v$, one of the rewards becomes invalid, reducing $x$ by $1$ and this can happen at most $2$ times during the whole process.
    144 * Else, the probability of drawing a pink slip increases by $\dfrac{v}{2}$.
    145 
    146 Notice that the probability of drawing a pink slip can never decrease.
    147 
    148 Now, since $v\geq 0.1$, each time we make a draw of the second type, the probability of drawing a pink slip increases by at least $0.05$. It will reach $1$ after just $20$ such draws. So, there will be at most $d=22$ draws before we are sure to get a pink slip.
    149 
    150 Simulating the whole process will take $\mathcal{O}(2^d)$ time which is sufficient in our case.
    151 
    152 What's left is just implementing the bruteforce solution taking care of precision errors while dealing with floating point numbers, especially while comparing $a$ with $v$ as this can completely change things up, keeping an item valid when it should become invalid. It follows that an error approximation of `1e-6` or smaller is sufficient while comparing any two values because all the numbers in the input have at most $4$ decimal places. Another alternative is to convert floating point numbers given in the input to integers using a scaling factor of $10^6$.
    153 
    154 **Time Complexity**
    155 
    156 $\mathcal{O}\big(2^{\frac{2}{v}}\big)$
    157 
    158 **Solution**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162 using namespace std;
    163 
    164 const long double eps = 1e-9;
    165 const long double scale = 1e+6;
    166 
    167 long double expectedRaces(int c,int m,int p,int v)
    168 {
    169     long double ans = p/scale;
    170     if(c>0)
    171     {
    172         if(c>v)
    173         {
    174             if(m>0)
    175                 ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v));
    176             else
    177                 ans += (c/scale)*(1+expectedRaces(c-v,0,p+v,v));
    178         }
    179         else
    180         {
    181             if(m>0)
    182                 ans += (c/scale)*(1+expectedRaces(0,m+c/2,p+c/2,v));
    183             else
    184                 ans += (c/scale)*(1+expectedRaces(0,0,p+c,v));
    185         }
    186     }
    187     if(m>0)
    188     {
    189         if(m>v)
    190         {
    191             if(c>0)
    192                 ans += (m/scale)*(1+expectedRaces(c+v/2,m-v,p+v/2,v));
    193             else
    194                 ans += (m/scale)*(1+expectedRaces(0,m-v,p+v,v));
    195         }
    196         else
    197         {
    198             if(c>0)
    199                 ans += (m/scale)*(1+expectedRaces(c+m/2,0,p+m/2,v));
    200             else
    201                 ans += (m/scale)*(1+expectedRaces(0,0,p+m,v));
    202         }
    203     }
    204     return ans;
    205 }
    206 
    207 int main()
    208 {
    209     int t;
    210     cin >> t;
    211     while(t--)
    212     {
    213         long double cd,md,pd,vd;
    214         cin >> cd >> md >> pd >> vd;
    215         int c = round(cd*scale);
    216         int m = round(md*scale);
    217         int p = round(pd*scale);
    218         int v = round(vd*scale);
    219         long double ans = expectedRaces(c,m,p,v);
    220         cout << setprecision(12) << fixed << ans << '\n';
    221     }
    222 }
    223 ```
    224 
    225 #### [D1: RPD and Rap Sheet (Easy Version)](https://codeforces.com/contest/1543/problem/D1)
    226 
    227 **Hint 1**
    228 
    229 In this version, $x\oplus z=y$ or in other words, $z=x\oplus y$ where $\oplus$ is the Bitwise XOR operator.
    230 
    231 **Hint 2**
    232 
    233 The number of queries allowed is equal to the number of possible initial passwords.
    234 
    235 **Hint 3**
    236 
    237 The grader provides us no information other than whether our guess was correct or not. So, we need to find a way to ask queries such that the $x$-th query will give the correct answer if the original password was $(x-1)$.
    238 
    239 **Hint 4**
    240 
    241 Try to ask queries in such a way that the $i$-th query reverses the effect of the $(i-1)$-th query and simultaneously checks if the initial password was $(i-1)$.
    242 
    243 **Hint 5**
    244 
    245 Try to use the self-inverse property of Bitwise XOR, *i.e.*, $a\oplus a=0$.
    246 
    247 **Tutorial**
    248 
    249 In this version of the problem, $k=2$. So, the $k$-itwise XOR is the same as Bitwise XOR.
    250 
    251 In case of incorrect guess, the system changes password to $z$ such that $x\oplus z=y$. Taking XOR with $x$ on both sides, $x\oplus x\oplus z=x\oplus y\implies z=x\oplus y$ because we know that $x\oplus x = 0$.
    252 
    253 Since the original password is less than $n$ and we have $n$ queries, we need to find a way to make queries such that if the original password was $(x-1)$, then the $x$-th query will be equal to the current password. There are many different approaches. I will describe two of them.
    254 
    255 **Method 1**
    256 
    257 Let $q_i$ denote the $i$-th query. Then,
    258 
    259 * $q_1=0$.
    260 * $q_i=(i-1)\oplus (i-2)$ for $2\leq i\leq n$.
    261 
    262 Let's see why this works.
    263 
    264 Claim — If the original password was $x$, after $i$ queries, the current password will be $x\oplus (i-1)$.
    265 
    266 **Proof**
    267 
    268 Let's prove this by induction.
    269 
    270 Base Condition — After $1$-st query, the password becomes $x\oplus 0=x\oplus(1-1)$.
    271 
    272 Induction Hypothesis — Let the password after $i$-th query be $x\oplus (i-1)$.
    273 
    274 Inductive step — The $(i+1)$-th query will be $i\oplus(i-1)$. If this is not equal to the current password, the password will change to $(x\oplus(i-1))\oplus(i\oplus(i-1))$ $=x\oplus(i-1)\oplus i\oplus(i-1)$ $=x\oplus i$ $=x\oplus((i+1)-1)$.
    275 
    276 Hence, proved by induction.
    277 
    278 Now notice that after $x$ queries, the password will become $x\oplus(x-1)$. And our $(x+1)$-th query will be $x\oplus(x-1)$ which is the same as the current password. So, the problem will be solved after $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved in at most $n$ queries.
    279 
    280 **Method 2 (Idea by KAN)**
    281 
    282 Again, let $q_i$ denote the $i$-th query. Then,
    283 
    284 $q_i=(i-1)\oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-2} \oplus q_{i-1}$
    285 
    286 Let's see why this works.
    287 
    288 Claim — If the original password was $x$, after $i$ queries, the current password will be $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}$.
    289 
    290 **Proof**
    291 
    292 Let's prove this by induction.
    293 
    294 Base Condition — The first query is $0$. After $1$-st query, the password becomes $x\oplus 0=x\oplus q_1$.
    295 
    296 Induction Hypothesis — Let the password after $i$-th query be $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}$.
    297 
    298 Inductive step — The $(i+1)$-th query will be $q_{i+1}$. So, the password after $(i+1)$-th query will be $(x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i})\oplus q_{i+1}$ $= x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}\oplus q_{i+1}$.
    299 
    300 Hence, proved by induction.
    301 
    302 Now notice that after $x$ queries, the password will become $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{x-1} \oplus q_{x}$. And our $(x+1)$-th query will be $x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{x-1} \oplus q_{x}$ which is the same as the current password. So, the problem will be solved after $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved in at most $n$ queries.
    303 
    304 But we are not done yet. We can't afford to calculate the value of each query naively in $\mathcal{O}(n)$ because this will time out. To handle this, we need to maintain a prefix XOR whose value will be $p=q_1\oplus q_2\oplus \ldots \oplus q_{i-1} \oplus q_i$ after $i$ queries. For the $(i+1)$-th query, find $q_{i+1}=p\oplus i$ and update $p=p\oplus q_{i+1}$.
    305 
    306 **Time Complexity**
    307 
    308 $\mathcal{O}(n)$ or $\mathcal{O}(n\cdot \log_{2} n)$ depending upon the implementation.
    309 
    310 **Solutions**
    311 
    312 **Solution 1**
    313 
    314 ```
    315 #include <bits/stdc++.h>
    316 using namespace std;
    317 
    318 int main()
    319 {
    320     int t=1;
    321     cin >> t;
    322     while(t--)
    323     {
    324         int n,k;
    325         cin >> n >> k;
    326         for(int i=0;i<n;i++)
    327         {
    328             if(i==0)
    329                 cout << 0 << endl;
    330             else
    331                 cout << (i^(i-1)) << endl;
    332             int v;
    333             cin >> v;
    334             if(v==1)
    335                 break;
    336         }
    337     }
    338     return 0;
    339 }
    340 ```
    341 
    342 **Solution 2**
    343 
    344 ```
    345 #include <bits/stdc++.h>
    346 using namespace std;
    347 
    348 int main()
    349 {
    350     int t=1;
    351     cin >> t;
    352     while(t--)
    353     {
    354         int n,k;
    355         cin >> n >> k;
    356         int p=0;
    357         for(int i=0;i<n;i++)
    358         {
    359             int q=p^i;
    360             cout << q << endl;
    361             p=p^q;
    362             int v;
    363             cin >> v;
    364             if(v==1)
    365                 break;
    366         }
    367     }
    368     return 0;
    369 }
    370 ```
    371 
    372 #### [D2: RPD and Rap Sheet (Hard Version)](https://codeforces.com/contest/1543/problem/D2)
    373 
    374 **Hint 1**
    375 
    376 The generalised $k$-itwise XOR does not satisfy the Self-Inverse property. So, the solution for the Easy Version won't work here.
    377 
    378 **Hint 2**
    379 
    380 Any property which is satisfied by $k$-its will also be satisfied by base $k$ numbers since a base $k$ number is nothing but a concatenation of $k$-its. So, try to prove properties for $k$-its as they are easier to work with.
    381 
    382 **Hint 3**
    383 
    384 Let $x_j$ denote the $j$-th $k$-it of $x$. Then, $x_j\oplus_k z_j=y_j$ $\forall$ valid $j$. Simplifying this,  
    385 $x_j\oplus_k z_j=y_j$ $\implies$ $(x_j+z_j)\bmod k=y_j$ $\implies$ $z_j=(y_j-x_j)\bmod k$ $\implies$ $z_j=(y_j\ominus_k x_j)$ where $a\ominus_k b$ operation is defined as $a\ominus_k b=(a-b)\bmod k$.
    386 
    387 **Hint 4**
    388 
    389 See Hints 2, 3 and 4 of the Easy Version.
    390 
    391 **Hint 5**
    392 
    393 Try to generalise the solutions for easy version by exploring properties of $\oplus_k$ and $\ominus_k$ operators.
    394 
    395 **Tutorial**
    396 
    397 Note — It is strongly recommended to read the proofs also to completely understand why the solutions work.
    398 
    399 The solutions described for the easy version won't work here because the general $k$-itwise operation does not satisfy self-inverse property, *i.e.*, $a\oplus_k a\neq 0$.
    400 
    401 In this whole solution, we will work in base $k$ only and we will convert the numbers to decimal only for I/O purpose. Notice that any property which is satisfied by $k$-its will also be satisfied by base $k$ numbers since a base $k$ number is nothing but a concatenation of $k$-its.
    402 
    403 When we make an incorrect guess, the system changes the password to $z$ such that $x\oplus_k z=y$. Let's denote the $j$-th $k$-it of $x$ by $x_j$. Expanding this according to the definition of $k$-itwise XOR, for all individual $k$-its $(x_j+z_j)\bmod k=y_j$ $\implies z_j=(y_j-x_j)\bmod k$. So, let's define another $k$-itwise operation $a\ominus_k b$ $= (a-b)\bmod k$. Then, $z=y\ominus_k x$. Now, let's extend the solutions of the Easy Version for this version.
    404 
    405 **Method 1**
    406 
    407 Before moving to the solution, let's see some properties of the $\ominus_k$ operation over $k$-its.
    408 
    409 Property 1 — $(a\ominus_k b)\ominus_k(a\ominus_k c)=c\ominus_k b$
    410 
    411 **Proof**
    412 
    413 $(a\ominus_k b)\ominus_k(a\ominus_k c)$ $= ((a-b)\bmod k - (a-c)\bmod k)\bmod k$ $=(a-b-a+c)\bmod k$ $=(c-b)\bmod k$ $= c\ominus_k b$
    414 
    415 Property 2 — $(b\ominus_k a)\ominus_k(c\ominus_k a)=b\ominus_k c$
    416 
    417 **Proof**
    418 
    419 $(b\ominus_k a)\ominus_k(c\ominus_k a)$ $= ((b-a)\bmod k - (c-a)\bmod k)\bmod k$ $=(b-a-c+a)\bmod k$ $=(b-c)\bmod k$ $= b\ominus_k c$
    420 
    421 Solution -
    422 
    423 Let $q_i$ denote the $i$-th query. Then,
    424 
    425 * $q_1=0$,
    426 * $q_i=(i-2)\ominus_k (i-1)$ if $i$ is even and
    427 * $q_i=(i-1)\ominus_k (i-2)$ if $i$ is odd.
    428 
    429 Let's see why this works.
    430 
    431 Claim — If the original password was $x$, after $i$ queries, the password becomes
    432 
    433 * $x\ominus_k (i-1)$ if $i$ is even and
    434 * $(i-1)\ominus_k x$ if $i$ is odd.
    435 
    436 **Proof**
    437 
    438 Let's prove this by induction.
    439 
    440 Base Case — $q_1=0$. So, after $1$-st query, the password becomes $0\ominus_k x = (1-1)\ominus_k x$.
    441 
    442 **Case 1 — $i$ is even**
    443 
    444 Induction hypothesis — Let the current password after $i$ queries be $x\ominus_k (i-1)$.
    445 
    446 Inductive step — $(i+1)$ is odd. So, the $(i+1)$-th query is $i\ominus_k (i-1)$. The new password will be $(i\ominus_k (i-1))\ominus_k(x\ominus_k (i-1))$ $= i\ominus_k x$ by Property 2.
    447 
    448 **Case 2 — $i$ is odd**
    449 
    450 Induction hypothesis — Let the current password after $i$ queries be $(i-1)\ominus_k x$.
    451 
    452 Inductive step — $(i+1)$ is even. So, the $(i+1)$-th query is $(i-1)\ominus_k i$. The new password will be $((i-1)\ominus_k i)\ominus_k((i-1)\ominus_k x)$ $= x\ominus_k i$ by Property 1.
    453 
    454 Hence, proved by induction.
    455 
    456 Now notice that after $x$ queries, the password will become $x\ominus_k (x-1)$ if $x$ is even or $(x-1)\ominus_k x$ if $x$ is odd which will be equal to the $(x+1)$-th query. Hence, the problem will be solved after exactly $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved after at most $n$ queries.
    457 
    458 **Method 2**
    459 
    460 Again, let's denote the $i$-th query by $q_i$.
    461 
    462 Then, $q_i=q_{i-1}\ominus_k\bigg[q_{i-2}\ominus_k\Big[q_{i-3}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k(i-1)]\big]\ldots\Big]\bigg]$
    463 
    464 Let's see why this works.
    465 
    466 Claim — If the original password was $x$, after $i$ queries, the password will be $q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$
    467 
    468 **Proof**
    469 
    470 Let's prove this by induction.
    471 
    472 Base Case — After the $1$-st query which is $0$, the password will be $0\ominus_k x = q_1\ominus_k x$.
    473 
    474 Induction hypothesis — Let the password after $i$ queries be $q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$
    475 
    476 Inductive Step — The $(i+1)$-th query is $q_{i+1}$. After $(i+1)$ queries, the password will becomes $q_{i+1}\ominus_k\Bigg[q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]\Bigg]$
    477 
    478 Hence, proved by induction.
    479 
    480 Now notice that after $x$ queries, the password will become $q_{x}\ominus_k\bigg[q_{x-1}\ominus_k\Big[q_{x-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$ which will be equal to the $(x+1)$-th query. Hence, the problem will be solved after exactly $(x+1)$ queries. Since $0\leq x \lt n$, the problem will be solved after at most $n$ queries.
    481 
    482 But we are not done yet. This solution is $\mathcal{O}(n^2)$ which will time out. The solution for this isn't as simple as what we did for the Easy version because the $\ominus_k$ operation is neither associative nor commutative. So, it's time to explore some more properties of these operations.
    483 
    484 Property 3 — $a\ominus_k(b\ominus_k c) = (a\ominus_k b)\oplus_k c$
    485 
    486 **Proof**
    487 
    488 $a\ominus_k(b\ominus_k c)$ $= (a-(b-c)\bmod k)\bmod k$ $= (a-b+c)\bmod k$ $= ((a-b)\bmod k+c)\bmod k$ $= (a\ominus_k b)\oplus_k c$
    489 
    490 Property 4 — $a\ominus_k(b\oplus_k c) = (a\ominus_k b)\ominus_k c$
    491 
    492 **Proof**
    493 
    494 $a\ominus_k(b\oplus_k c)$ $= (a-(b+c)\bmod k)\bmod k$ $= (a-b-c)\bmod k$ $= ((a-b)\bmod k-c)\bmod k$ $= (a\ominus_k b)\ominus_k c$
    495 
    496 Now, let's try to simplify our queries.
    497 
    498 * $q_1=0$
    499 * $q_2=q_1\ominus_k 1$
    500 * $q_3=q_2\ominus_k [q_1\ominus_k 2]=[q_2\ominus_k q_1]\oplus_k 2$ (by Property 3)
    501 * $q_4=q_3\ominus_k \big[q_2\ominus_k [q_1\ominus_k 3]\big]=q_3\ominus_k \big[[q_2\ominus_k q_1]\oplus_k 3\big]=\big[q_3\ominus_k[q_2\ominus_k q_1]\big]\ominus_k 3$ (by Property 4)
    502 * $\ldots$
    503 
    504 See the pattern?
    505 
    506 You can generalize the $i$-th query as -
    507 
    508 * $q_i=q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\big[q_{i-3}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]\oplus_k (i-1)$ if $i$ is odd
    509 * $q_i=q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\big[q_{i-3}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]\ominus_k (i-1)$ if $i$ is even
    510 
    511 So, we will maintain a prefix Negative XOR whose value after $i$ queries will be $p=q_{i}\ominus_k\Big[q_{i-1}\ominus_k\big[q_{i-2}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]$
    512 
    513 Then,
    514 
    515 * $q_{i+1}=p\ominus_k i$ if $i$ is odd
    516 * $q_{i+1}=p\oplus_k i$ if $i$ is even
    517 
    518 Then update $p=q_{i+1}\ominus_k p$
    519 
    520 **Notes**
    521 
    522 * Both the operations $\ominus_k$ and $\oplus_k$ can be implemented naively by converting the decimal numbers to base $k$, finding the $k$-itwise XOR of the base $k$ numbers and finally converting it back to decimal. The time complexity for each of these operations will be $\mathcal{O}(\log_k n)$.
    523 * At any stage, the maximum number that we could be dealing with will be non-negative and will not exceed $n\times k$ as the $k$-itwise operations do not add extra $k$-its. This fits well within the limits of $y$ which is $2\cdot 10^7$.
    524 * The total time complexity of the solution will be $\mathcal{O}(n\log_k n)$.
    525 
    526 **Solutions**
    527 
    528 **Solution 1**
    529 
    530 ```
    531 #include <bits/stdc++.h>
    532 using namespace std;
    533 
    534 int knxor(int x,int y,int k)
    535 {
    536     int z=0;
    537     int p=1;
    538     while(x>0 || y>0)
    539     {
    540         int a=x%k;
    541         x=x/k;
    542         int b=y%k;
    543         y=y/k;
    544         int c=(a-b+k)%k;
    545         z=z+p*c;
    546         p=p*k;
    547     }
    548     return z;
    549 }
    550 
    551 int main()
    552 {
    553     int t=1;
    554     cin >> t;
    555     while(t--)
    556     {
    557         int n,k;
    558         cin >> n >> k;
    559         for(int i=0;i<n;i++)
    560         {
    561             if(i==0)
    562                 cout << 0 << endl;
    563             else if(i%2==0)
    564                 cout << knxor(i,i-1,k) << endl;
    565             else
    566                 cout << knxor(i-1,i,k) << endl;
    567             int v;
    568             cin >> v;
    569             if(v==1)
    570                 break;
    571         }
    572     }
    573     return 0;
    574 }
    575 ```
    576 
    577 **Solution 2**
    578 
    579 ```
    580 #include <bits/stdc++.h>
    581 using namespace std;
    582 
    583 int knxor(int x,int y,int k)
    584 {
    585     int z=0;
    586     int p=1;
    587     while(x>0 || y>0)
    588     {
    589         int a=x%k;
    590         x=x/k;
    591         int b=y%k;
    592         y=y/k;
    593         int c=(a-b+k)%k;
    594         z=z+p*c;
    595         p=p*k;
    596     }
    597     return z;
    598 }
    599 
    600 int kxor(int x,int y,int k)
    601 {
    602     int z=0;
    603     int p=1;
    604     while(x>0 || y>0)
    605     {
    606         int a=x%k;
    607         x=x/k;
    608         int b=y%k;
    609         y=y/k;
    610         int c=(a+b)%k;
    611         z=z+p*c;
    612         p=p*k;
    613     }
    614     return z;
    615 }
    616 
    617 int main()
    618 {
    619     int t=1;
    620     cin >> t;
    621     while(t--)
    622     {
    623         int n,k;
    624         cin >> n >> k;
    625         int p=0;
    626         for(int i=0;i<n;i++)
    627         {
    628             if(i==0)
    629                 cout << 0 << endl;
    630             else if(i%2==0)
    631             {
    632                 int q = kxor(p,i,k);
    633                 cout << q << endl;
    634                 p=knxor(q,p,k);
    635             }
    636             else
    637             {
    638                 int q = knxor(p,i,k);
    639                 cout << q << endl;
    640                 p=knxor(q,p,k);
    641             }
    642             int v;
    643             cin >> v;
    644             if(v==1)
    645                 break;
    646         }
    647     }
    648     return 0;
    649 }
    650 ```
    651 
    652 **About the Adaptive Grader**
    653 
    654 This part may be interesting for hackers and those who would like to understand what goes in the background checkers and interactors which determine the correctness of their solutions.
    655 
    656 You must have noticed a large number of submissions failing on Test 1 itself. If you check the checker logs of those solutions, you will find that they fail on many different test cases although the test itself has 1 or 2 test cases. This is because the grader is also adaptive apart from the Rap Sheet System being adaptive. The initial password is not fixed and the grader checks if the solution will give correct answer or not for all possible initial passwords in just a single run! Here is how this is implemented.
    657 
    658 The grader maintains a set which initially contains all possible initial passwords. Whenever you ask a query, the grader finds out which initial password will give correct answer for this query. This is found using the generalised expression of queries derived in the Method 2 solution. Take some time to convince yourself that this initial password will be unique. It then removes this initial password from the set if it still exists. After that, if the set is empty, the grader returns 1 (meaning that there is no other password for which the solution can give Wrong Answer), otherwise 0 (obviously after checking the constraints on $y$). In this way, only a solution which gives correct answers for all possible initial passwords for a particular $n$ and $k$ defined in the input will manage to pass.
    659 
    660 Sometimes, checkers and adaptive interactors are more difficult to write than the solution itself! This was one such case.
    661 
    662 #### [E: The Final Pursuit](https://codeforces.com/contest/1543/problem/E)
    663 
    664 **Hint 1**
    665 
    666 In a simple $n$-Dimensional Hypercube, two vertices are connected if and only if they differ by exactly $1$ bit in their binary representation.
    667 
    668 **Hint 2**
    669 
    670 The $n$-Dimensional Hypercubes are highly symmetric and all vertices are equivalent.
    671 
    672 **Hint 3**
    673 
    674 If we select a particular vertex, then all directions in which the edges connected to it goes are also equivalent.
    675 
    676 **Hint 4**
    677 
    678 For any two vertices $a$ and $b$ separated at a distance of exactly $2$, there are exactly $2$ vertices connected to both $a$ and $b$.
    679 
    680 **Hint 5**
    681 
    682 Any permuted $n$-Dimensional Hypercube is isomorphic to the simple $n$-Dimensional Hypercube. So, its structure is same as the simple $n$-Dimensional Hypercube.
    683 
    684 **Hint 6**
    685 
    686 You can find the permutation greedily
    687 
    688 **Tutorial: Part 1 - Finding the Permutation**
    689 
    690 Before moving to the solution, notice a very important property of simple $n$-Dimensional Hypercubes — Two vertices $a$ and $b$ are connected if and only if $a$ and $b$ differ by exactly one bit in their binary representations.
    691 
    692 The permutation can be found using the following greedy algorithm — First, assign any arbitrary vertex as $p_0$. This is obvious since all vertices are equivalent. Then, in the simple $n$-Dimensional Hypercube, all powers of $2$ must be connected to the vertex $0$. Moreover, these vertices are added only when we are adding another dimension to the cube. Since all directions are also equivalent, it does not matter in which direction we add a new dimension. So, we can assign all the $n$ vertices connected to $p_0$ in the permuted $n$-Dimensional Hypercube as $p_1$, $p_2$, $p_4$, $p_8$, $\ldots$, $p_{2^{n-1}}$ in any arbitrary order. Now, we will find $p_u$ for the remaining vertices in increasing order of $u$.
    693 
    694 In order to find $p_u$, first find a set $S$ of vertices $v$ such that $v \lt u$ and $v$ is connected to $u$ in the simple $n$-Dimensional Hypercube. Then find any vertex $w$ connected to all the vertices $p_v$ such that $v\in S$ in the permuted $n$-Dimensional Hypercube and assign $p_u=w$. I claim that we can never make a wrong choice because we will never have a choice! There will only be one such vertex $w$ for any $u$. Let's prove it.
    695 
    696 **Proof**
    697 
    698 Consider two vertices $v_1$ and $v_2$ in the set $S$. These vertices will differ by exactly $2$ bits in their binary representation. Let the bits in which they differ be $b_x$ and $b_y$. Then, they will have the form $v_1=\ldots b_x\ldots b_y\ldots$ and $v_2=\ldots b^{'}_{x}\ldots b^{'}_{y}\ldots$ where $\ldots$ represent the same bits. Now, only two vertices $u_1=\ldots b_{x}\ldots b^{'}_{y}\ldots$ and $u_2=\ldots b^{'}_{x}\ldots b_{y}\ldots$ can be connected to both $v_1$ and $v_2$. Since a permuted $n$-Dimensional Hypercube is isomorphic to a simple $n$-Dimensional Hypercube, there will only be two vertices connected to both $p_{v_1}$ and $p_{v_2}$ in the permuted $n$-Dimensional Hypercube also.
    699 
    700 If we iterate over $u$ in increasing order, then $b_x\neq b_y$, otherwise one of $v_1$ or $v_2$ will be greater than $u$ which is a contradiction. So, the only vertices connected to both $v_1$ and $v_2$ will have the forms $u_1=\ldots 0\ldots 0\ldots$ and $u_2=\ldots 1\ldots 1\ldots$. Now since $u_1 \lt v_1$ and $u_1 \lt v_2$, $p_{u_1}$ has already been calculated and so, one of the vertex connected to both $p_{v_1}$ and $p_{v_2}$ in the permuted $n$-Dimensional Hypercube has already been used. So, we are left with only one choice for such a vertex $w$.
    701 
    702 **Alternate method of finding the permutation (by mshiladityam)**
    703 
    704 Let's call the vertex connected to a given vertex and which is in the opposite constituent smaller hypercube the ***image*** of the given vertex.
    705 
    706 Lemma — if there is an edge $(a, b)$ in the $n$-Dimensional hypercube where vertices $a$ and $b$ lie in different constituent $(n-1)$-Dimensional Hypercubes (in other words, $a$ and $b$ are images of each other), then for all vertices $q$ adjacent to $a$, the image of $q$ is adjacent to $b$.
    707 
    708 This lemma can be proved by using the fact that two vertex are connected if and only if they differ by exactly $1$ bit.
    709 
    710 Select any two vertices $a$ and $b$. They form a starting point: we treat them as two vertices in opposite constituents (by symmetry, we can prove that any pairs can be treated as such).
    711 
    712 Now let us perform *multisource BFS* with $a$ and $b$ as source nodes. Due to the lemma, the nodes which are discovered from $a$ first lie in the component of $a$, and those which are discovered from $b$ first lie in the component of $b$ (it is easy again to prove it using induction on depth of already discovered vertices). So we have separated these two constituent smaller dimension hypercubes. Lets call a recursive function on any one of them: this recursive function returns a permutation which transforms the permutated hypercube to the simple hypercube. Now, we find for each vertex, in the constituent hypercube whose permutation we just found, its image. Then we can find the permutation for the other constituent by just adding $2^{n-1}$ to the corresponding image. Hence we perform the merging process of recursion.
    713 
    714 The time complexity of this approach is $\mathcal{O}(n\cdot 2^{n})$
    715 
    716 **Hint 7**
    717 
    718 Instead of colouring the permuted $n$-Dimensional Hypercube, try to colour the simple $n$-Dimensional Hypercube and map these colours to the permuted one in the end using the permutation found in Part 1.
    719 
    720 **Hint 8**
    721 
    722 The number of vertices of each colour will be equal.
    723 
    724 **Hint 9**
    725 
    726 Try to colour a simple $4$-Dimensional Hypercube. This is not a graph problem, rather a constructive problem.
    727 
    728 **Hint 10**
    729 
    730 The way in which vertices are connected in a simple $n$-Dimensional Hypercube suggests something related to Bitwise XOR.
    731 
    732 **Tutorial: Part 2 - Colouring the Hypercube**
    733 
    734 Let's try to colour the simple $n$-Dimensional Hypercube instead of the permuted one. We can map the colours to the permuted one in the end using the permutation found in Part 1.
    735 
    736 I claim that if $n$ is not a power of $2$, then no colouring exists. A simple explanation is that the graph is symmetric and also the colours. So, it is natural that the number of vertices of each colour must be equal meaning $2^n$ must be divisible by $n$ or in other words, $n$ must be a power of $2$ itself. But if symmetry doesn't satisfy you, I have a formal proof too.
    737 
    738 **Proof**
    739 
    740 According to the condition, every vertex must be connected to at least one vertex of every colour or equivalently, *exactly* one vertex of every colour since there are $n$ colours and $n$ neighbours of each vertex. So, if we consider the set of neighbours of any vertex, every colour will appear exactly once in that set. If we consider the multi-set of neighbours of all vertices, every colour will appear $2^n$ times in that set. But every vertex has been counted $n$ times in this multi-set because a particular vertex is the neighbour of $n$ other vertices. So, if we consider the set of all vertices, every colour will appear $\frac{2^n}{n}$ times in that set. Obviously, this number must be a whole number. So, $2^n$ must be divisible by $n$ or in other words, $n$ must itself be a power of $2$ for a colouring to exist. Otherwise, it doesn't exist. To show that a colouring exists if $n$ is a power of $2$, we will construct a colouring.
    741 
    742 **Construction -** This is the most interesting and difficult part of the whole problem. The following construction works —
    743 
    744 Consider a vertex $u$. Let its binary representation be $b_{n-1}b_{n-2}\ldots b_2 b_1 b_0$. Then the colour of this vertex will be $\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$. Let's show why this works.
    745 
    746 * $\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$ will always lie between $0$ and $n-1$ inclusive because $n$ is a power of $2$.
    747 * If we are at a vertex $u$ with a colour $c_1$ and we want to reach a vertex of colour $c_2$, we can reach the vertex $v=u\oplus(1\ll (c_1\oplus c_2))$. This is a vertex adjacent to $u$ since it differs from it by exactly $1$ bit and this is the $(c_1\oplus c_2)$-th bit. Notice that the colour of this vertex $v$ will be $c_1\oplus (c_1\oplus c_2) = c_2$.
    748 * $(c_1\oplus c_2)$ will always lie between $0$ and $n-1$ because $n$ is a power of $2$. So, $v$ will always be a valid vertex number.
    749 
    750 You can see that many of these facts break when $n$ is not a power of $2$. So, this colouring will not work in such cases.
    751 
    752 Finally, after colouring the simple hypercube, we need to restore the vertex numbers of the permuted hypercube. This can be simply done by replacing all vertices $u$ with $p_u$ using the permutation we found in Part 1.
    753 
    754 **Visualise the Colouring**
    755 
    756 Well, that's enough of theoretical stuff. For those who like visualising things, here is a 4-D Hypercube and its colouring -
    757 
    758 ![4D Cube](/predownloaded/f9/0a/f90a29303a28809bfe2782db3774b44e7d759344.png)
    759 
    760 **Time Complexity**
    761 
    762 Finding the permutation takes $\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$ time if implemented using set or $\mathcal{O}(n^2\cdot 2^n)$ time if implemented using vector. Constructing the colouring for the simple $n$-Dimensional Hypercube takes $\mathcal{O}(n\cdot 2^n)$ time. Restoring colours for the permuted $n$-Dimensional Hypercube takes $\mathcal{O}(2^n)$ time.
    763 
    764 So, the overall time complexity is $\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$ or $\mathcal{O}(n^2\cdot 2^n)$ depending upon implementation.
    765 
    766 **Solution**
    767 
    768 ```
    769 #include <bits/stdc++.h>
    770 using namespace std;
    771 
    772 void permuteHypercube(int n,int m,vector<int> adj[],set<int> s[],int p[])
    773 {
    774     for(int i=0;i<m;i++)
    775         p[i]=-1;
    776     bool used[m];
    777     for(int i=0;i<m;i++)
    778         used[i]=false;
    779     p[0]=0;
    780     used[0]=true;
    781     for(int u=1;u<m;u++)
    782     {
    783         vector<int> req;
    784         for(int i=0;i<n;i++)
    785         {
    786             int v=u^(1<<i);
    787             if(v<u)
    788                 req.push_back(v);
    789         }
    790         if(req.size()==1)
    791         {
    792             int v=req[0];
    793             for(int i=0;i<adj[p[v]].size();i++)
    794             {
    795                 int w=adj[p[v]][i];
    796                 if(used[w])
    797                     continue;
    798                 p[u]=w;
    799                 used[w]=true;
    800                 break;
    801             }
    802         }
    803         else
    804         {
    805             int v=req[0];
    806             for(int i=0;i<adj[p[v]].size();i++)
    807             {
    808                 int w=adj[p[v]][i];
    809                 if(used[w])
    810                     continue;
    811                 if(s[w].find(p[req[1]])!=s[w].end())
    812                 {
    813                     p[u]=w;
    814                     used[w]=true;
    815                     break;
    816                 }
    817             }
    818         }
    819     }
    820 }
    821 
    822 int main()
    823 {
    824     ios_base::sync_with_stdio(false);
    825     cin.tie(NULL);
    826     int t;
    827     cin >> t;
    828     while(t--)
    829     {
    830         int n;
    831         cin >> n;
    832         int m = (1<<n);
    833         int p[m];
    834         set<int> s[m];
    835         vector<int> adj[m];
    836         for(int i=0;i<n*m/2;i++)
    837         {
    838             int u,v;
    839             cin >> u >> v;
    840             adj[u].push_back(v);
    841             adj[v].push_back(u);
    842             s[u].insert(v);
    843             s[v].insert(u);
    844         }
    845         permuteHypercube(n,m,adj,s,p);
    846         for(int i=0;i<m;i++)
    847             cout << p[i] << " ";
    848         cout << '\n';
    849         if(n!=1 && n!=2 && n!=4 && n!=8 && n!=16)
    850         {
    851             cout << -1 << '\n';
    852             continue;
    853         }
    854         int temp[m];
    855         for(int i=0;i<m;i++)
    856         {
    857             int clr=0;
    858             for(int j=0;j<n;j++)
    859             {
    860                 if(i&(1<<j))
    861                     clr=clr^j;
    862             }
    863             temp[i]=clr;
    864         }
    865         int c[m];
    866         for(int i=0;i<m;i++)
    867             c[p[i]]=temp[i];
    868         for(int i=0;i<m;i++)
    869             cout << c[i] << " ";
    870         cout << '\n';
    871     }
    872 }
    873 ```
    874 
    875 **Alternative Solution (by mshiladityam)**
    876 
    877 ```
    878 #include <iostream>
    879 #include <iomanip>
    880 #include <vector>
    881 #include <cmath>
    882 #include <algorithm>
    883 #include <set>
    884 #include <utility>
    885 #include <queue>
    886 #include <map>
    887 #include <assert.h>
    888 #include <stack>
    889 #include <string>
    890 #include <ctime>
    891 #include <chrono>
    892 #include <random>
    893 using namespace std;
    894  
    895 const int MAX=65536;
    896 int power[21]={0};
    897 vector<int> adj[MAX+1];
    898 bool xtra[MAX+1];
    899 bool in[MAX+1];
    900 vector<int> f(vector<int> s)
    901 //given a set of vertices [graph], returns the permutation that was applied to the simple hypercube to get this graph
    902 {
    903 	/*
    904 	cout << "set\n";
    905 	for (auto it : s)
    906 	{
    907 		cout << it << " ";
    908 	}
    909 	cout << '\n';
    910 	*/
    911 	if ((int)s.size()==2)
    912 	{
    913 		vector<int> p(2);
    914 		p[0]=s[0];
    915 		p[1]=s[1];
    916 		return p;
    917 	}
    918 	for (auto i: s) in[i]=true;
    919 	int v1=s[0];
    920 	int v2=-1;
    921  
    922 	for (auto i: adj[v1])
    923 	{
    924 		if (in[i])
    925 		{
    926 			v2=i;
    927 			break;
    928 		}
    929 	}
    930 	assert(v2!=-1);
    931 	//cout << "v1= " << v1 << " v2 = " << v2 << '\n';
    932 	vector<int> component;
    933 	//multisource BFS from (v1, v2)
    934 	{
    935 		queue<int> q;
    936 		q.push(v1);
    937 		q.push(v2);
    938 		map<int, bool> vis;
    939 		vis[v1]=true;
    940 		vis[v2]=true;
    941 		map<int, bool> cmp;
    942 		cmp[v1]=true;
    943 		component.push_back(v1);
    944 		while (!q.empty())
    945 		{
    946 			auto u=q.front();
    947 			q.pop();
    948 			for (auto i: adj[u])
    949 			{
    950 				if ((!vis[i])&&in[i])
    951 				{
    952 					vis[i]=true;
    953 					q.push(i);
    954 					cmp[i]=cmp[u];
    955 					if (cmp[i]) component.push_back(i);
    956 				}
    957 			}
    958 		}
    959 	}
    960 	for (auto i: s) in[i]=false;
    961 	for (auto i: component) in[i]=true;
    962 	vector<int> p1=f(component);
    963 	for (auto i: s) in[i]=true;
    964 	for (auto i: component) xtra[i]=true;
    965 	
    966 	vector<int> p((int)s.size());
    967 	
    968 	int z=component.size();
    969 	assert(2*z==(int)s.size());
    970 	
    971 	for (int i=0; i<z; i++) p[i]=p1[i];
    972 	
    973 	for (int i=0; i<z; i++)
    974 	{
    975 		//i+z
    976 		int g=-1;
    977 		for (auto i: adj[p[i]])
    978 		{
    979 			if (in[i]&&(!xtra[i]))
    980 			{
    981 				g=i;
    982 				break;
    983 			}
    984 		}
    985 		assert(g!=-1);
    986 		p[z+i]=g;
    987 	}
    988 	for (auto i: component) xtra[i]=false;
    989 	for (auto i: s) in[i]=false;
    990 	return p;
    991 }
    992  
    993 vector<int> colorit(int n)
    994 {
    995 	vector<int> ret(n);
    996 	for (int i=0; i<n; i++)
    997 	{
    998 		int res=0;
    999 		for (int z=0; z<20; z++) res^=z*((power[z]&i)!=0);
   1000 		ret[i]=res;
   1001 	}
   1002 	return ret;
   1003 }
   1004  
   1005 void solve()
   1006 {
   1007 	int n;
   1008 	cin>>n;
   1009 	for (int i = 0; i < power[n]; i++) adj[i].clear();
   1010 	for (int j = 0; j < n * power[n - 1]; j++)
   1011 	{
   1012 		int u, v;
   1013 		cin >> u >> v;
   1014 		adj[u].push_back(v);
   1015 		adj[v].push_back(u);
   1016 	}
   1017 	vector<int> p;
   1018 	
   1019 	{
   1020 		vector<int> s;
   1021 		for (int i=0; i<power[n]; i++) s.push_back(i);
   1022 		p=f(s);
   1023 	}
   1024 	
   1025 	for (int i=0; i<power[n]; i++) cout<<p[i]<<' ';
   1026 	cout<<'\n';
   1027 	
   1028 	if (power[n]%n)
   1029 	{
   1030 		cout<<-1<<'\n';
   1031 		return;
   1032 	}
   1033 	vector<int> col=colorit(power[n]);
   1034 	vector<int> out(power[n]);
   1035 	for (int i=0; i<power[n]; i++)
   1036 	{
   1037 		out[p[i]]=col[i];
   1038 	}
   1039 	for (int i=0; i<power[n]; i++) cout<<out[i]<<' ';
   1040 	cout<<'\n';
   1041 	return;
   1042 }
   1043  
   1044 signed main()
   1045 {
   1046 	ios::sync_with_stdio(0);
   1047 	cin.tie(NULL); cout.tie(NULL);
   1048 	int t;
   1049 	cin >> t;
   1050 	//t=1;
   1051 	
   1052 	power[0]=1;
   1053 	for (int j=1; j<=20; j++) power[j]=power[j-1]*2;
   1054 	
   1055 	while (t--)
   1056 	{
   1057 		solve();
   1058 	}
   1059 	return 0;
   1060 }
   1061 ```