codeforces-scrape

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

2155.md (21391B)


      1 Source: https://codeforces.com/blog/entry/147174
      2 
      3 Hello, Codeforces!
      4 
      5 Sorry for the late editorial. Our national olympiad just finished and we were sorting everything out.
      6 
      7 We also apologize for weak tests on D that made an incorrect solution pass. Many testers submitted the same solution and we mistakenly thought that it was correct given the low bound on the number of batteries. Still, we hope that the contest was a fun and valuable experience for all contestants.
      8 
      9 The editorial was prepared by [efishel](/profile/efishel "Мастер efishel") and me. If you have any questions about the problems or the solutions, please ask in the comments.
     10 
     11 ### [2155A - Эль фучо](/contest/2155/problem/A "Codeforces Round 1056 (Div. 2)")
     12 
     13 **Hint 1**
     14 
     15 When two teams in the same group face off against each other, exactly one of them stays in the group.
     16 
     17 **Solution 1**
     18 
     19 The answer for all $n$ is $2n-2$.
     20 
     21 Let's consider the winners' group first. Note that exactly one team drops to the losers' bracket for every match in this group. Only one team is left in the winners' group right before the end, so $n-1$ matches must have been played in the winners' group right before the final match.
     22 
     23 Similar logic applies to the losers' group. $n-1$ teams in total drop down to the losers' group over the course of the tournament. For every match played between two teams in this group, exactly one team is eliminated from the tournament. A single team in left in this group right before the final match, so $n-2$ matches must have been played in the losers' group right before the final match.
     24 
     25 Finally, we add the final match to our calculation, bringing the total to
     26 
     27 $(n-1)+(n-2)+1 = 2n-2$
     28 
     29 **Code (C++)**
     30 
     31 ```
     32 #include <bits/stdc++.h>
     33 
     34 using namespace std;
     35 
     36 int main() {
     37 
     38   int n, t; 
     39 
     40   cin >> t;
     41 
     42   while(t--) {
     43 
     44      cin >> n;
     45 
     46      cout << 2*n-2 << "\n";
     47 
     48   }
     49 
     50 }
     51 ```
     52 
     53 **Solution 2**
     54 
     55 Alternatively, we can simulate the process directly.
     56 
     57 Suppose there are $a$ teams in the winners' group and $b$ teams in the losers' group right before a round.
     58 
     59 First, $\left \lfloor \frac{b}{2} \right \rfloor$ matches are played among the teams in the losers' group, so $\left \lfloor \frac{b}{2} \right \rfloor$ are eliminated in this step. We subtract this number from $b$ and add $\left \lfloor \frac{b}{2} \right \rfloor$ to the total number of matches played.
     60 
     61 Then, $\left \lfloor \frac{a}{2} \right \rfloor$ matches are played among the teams in the winners' group, so $\left \lfloor \frac{a}{2} \right \rfloor$ of them drop down to the losers' group. We subtract this number from $b$ and add $\left \lfloor \frac{b}{2} \right \rfloor$ to the total number of matches played.
     62 
     63 After simulating $\mathcal{O}(\log (n))$ rounds as described above, both brackets are left with a single team, so we add $1$ to our total.
     64 
     65 Time complexity: $\mathcal{O}(\log (n))$
     66 
     67 **Code (C++)**
     68 
     69 ```
     70 #include <bits/stdc++.h>
     71  
     72 using namespace std;
     73  
     74 int main() {
     75 	
     76 	int n, t, winners, losers, ans;
     77 	
     78 	cin >> t;
     79 	
     80 	while(t--) {
     81 	   cin >> n;
     82 	   winners = n;
     83 	   losers = 0;
     84 	   ans = 0;
     85 	   
     86 	   while(max(losers, winners) > 1) {
     87 	       ans += losers/2;
     88 	       losers = (losers+1)/2;
     89 	       
     90 	       ans += winners/2; 
     91 	       losers += winners/2; 
     92 	       winners++;
     93 	       winners /= 2;
     94 	   }
     95 	   
     96 	   ans++;
     97 	   
     98 	   cout << ans << "\n";
     99 	}
    100 }
    101 ```
    102 
    103 ### [2155B - Великий побег Авраама](/contest/2155/problem/B "Codeforces Round 1056 (Div. 2)")
    104 
    105 **Hint 1**
    106 
    107 There is exactly one value of $k$ that doesn't work
    108 
    109 **Hint 2**
    110 
    111 Two arrows facing each other trap Abraham forever.
    112 
    113 **Solution**
    114 
    115 We claim that the only value of $k$ for which the answer is $\texttt{NO}$ is $k = n*n-1$.
    116 
    117 If $k = n^2-1$ were possible, Abraham should be trapped forever from exactly $n^2-(n^2-1) = 1$ starting cell, but the arrow in that cell would necessarily point towards the outside of the grid, or in the direction of another cell from which Abraham will eventually escape, so this situation is impossible and we should print $\texttt{NO}$.
    118 
    119 All other values of $k$ are achievable with the following construction:
    120 
    121 1. Fill up rows of the grid with $\texttt{U}$ from left to right and from top to bottom. You should place $k$ of this letter in total.
    122 2. Fill every cell that doesn't have a $\texttt{U}$ already and isn't in the last row with a $\texttt{D}$. (These cells might be non-existent)
    123 3. Fill the leftmost unoccupied cell in the last row with an $R$ and all the cells to its right with an $L$. (Note that at least one $L$ is placed).
    124 
    125 This works because, if Abraham steps on a $\texttt{U}$, he will be pushed onto another $\texttt{U}$, and so on until he leaves the board.
    126 
    127 On the other hand, if he steps on a $\texttt{D}$, he will be carried along all the way to an $\texttt{R}$ or $\texttt{L}$ in the last row. It's easy to see that these directions necessarily trap Abraham.
    128 
    129 Time complexity: $\mathcal{O}(n^2)$
    130 
    131 **Code (Python)**
    132 
    133 ```
    134 t = int(input())
    135  
    136 for q in range(t):
    137     n, k = (int(x) for x in input().split())
    138  
    139     if(k == n*n-1):
    140         print("NO")
    141     else:
    142         print("YES")
    143         for i in range(n):
    144  
    145             s = ""
    146             for j in range(n):
    147                 if(k > 0):
    148                     s += "U"
    149                     k -= 1
    150                 elif(i == n-1 and j == n-1):
    151                     s += "L"
    152                 elif(i == n-1):
    153                     s += "R"
    154                 else:
    155                     s += "D"
    156  
    157             print(s)
    158 ```
    159 
    160 ### [2155C - Плащи древних волшебников](/contest/2155/problem/C "Codeforces Round 1056 (Div. 2)")
    161 
    162 **Hint 1**
    163 
    164 What's the maximum value that $|a_{i+1} - a_i|$ can attain for any $i$?
    165 
    166 **Hint 2**
    167 
    168 Bound the number of possible cape arrangements
    169 
    170 **Solution**
    171 
    172 Suppose that Harry's list corresponds to at least one arrangement of capes. The main claim is that any two consecutive values in his list differ by at most $1$.
    173 
    174 Note that when Harry walks from position $i$ to position $i+1$, the visibility of wizard $1$ to $i-1$ and $i+2$ to $n$ is unaffected, so there are four possible situations regarding the other $2$ wizards:
    175 
    176 * Wizards $i$ and $i+1$ wear their capes to their left. Wizard $i+1$ becomes visible and wizard $i$ can still be seen from position $i+1$, so $a_{i+1}-a_i = 1$
    177 * Wizards $i$ and $i+1$ wear their capes to their right. Wizard $i+1$ remains visible while wizard $i$ becomes invisible from position $i+1$, so $a_{i+1}-a_i = -1$
    178 * Wizard $i$ wears his cape to his left while wizard $i+1$ wears his cape to his right. Both wizards are still visible from position $i+1$, so $a_{i+1}-a_i = 0$
    179 * Wizard $i$ wears his cape to his left while wizard $i+1$ wears his cape to his right. Wizard $i+1$ becomes visible, but wizard $i$ becomes invisible when moving to position $i+1$, so $a_{i+1}-a_i = 0$
    180 
    181 In summary, if both wizards wear their capes the same way, the difference between the corresponding entries in Harry's list is $1$. Else, it is $0$. Note that this determines a unique possibility (it might be invalid) for the entire cape arrangement based on how wizard $1$ is wearing his cape only if $|a_{i+1}-a_i| \lt 2$ for all $1 \le i \lt n$.
    182 
    183 Thus, there are at most two possible arrangements for the wizards' capes. We can construct both of them and check whether they are consistent with Harry's list.
    184 
    185 Time complexity: $\mathcal{O}(n)$
    186 
    187 **Code (Python)**
    188 
    189 ```
    190 def validar(x, n, a):
    191     flag = False
    192     visibles = 1
    193  
    194     for i in range(2, n+1):
    195         if(x[i] == 1):
    196             visibles += 1
    197  
    198     if(visibles == a[1]):
    199         flag = True
    200  
    201         for i in range(1, n):
    202             if(x[i] == 1 and x[i+1] == 1):
    203                 visibles -= 1
    204             elif(x[i] == 0 and x[i+1] == 0):
    205                 visibles += 1
    206  
    207             if(a[i+1] != visibles):
    208                 flag = False
    209                 break
    210  
    211     return flag
    212  
    213 t = int(input())
    214  
    215 for i in range(t):
    216     sol1 = []
    217     sol2 = []
    218     sol1.append(0)
    219     sol2.append(0)
    220     sol1.append(0)
    221     sol2.append(1)
    222     flag = True
    223     cont = 0
    224     
    225     n = int(input())
    226     arr = []
    227     arr.append(0)
    228     arr.extend(map(int, input().split()))
    229  
    230     for j in range(1, n): 
    231         if(arr[j+1]-arr[j] > 1):
    232             flag = False
    233             break
    234  
    235         if(arr[j+1]-arr[j] == 0):
    236             sol1.append(1-sol1[j])
    237             sol2.append(1-sol2[j])
    238         else:
    239             sol1.append(sol1[j])
    240             sol2.append(sol2[j])
    241  
    242     if(not flag):
    243         print(0)
    244         continue
    245  
    246     if(validar(sol1, n, arr)):
    247         cont += 1
    248  
    249     if(validar(sol2, n, arr)):
    250         cont += 1
    251  
    252     print(cont)
    253 ```
    254 
    255 ### [2155D - Батарейки](/contest/2155/problem/D "Codeforces Round 1056 (Div. 2)")
    256 
    257 **Hint 1**
    258 
    259 Place the batteries in order on a circumference.
    260 
    261 **Hint 2**
    262 
    263 If there are $a$ working batteries, can we bound the distance between some pair of them in terms of $n$ and $a$?
    264 
    265 **Solution**
    266 
    267 Arrange the batteries in clockwise order on a circumference such that the arc length between any two consecutive batteries is $1$, and let the indices of the working batteries be $1 \le b_1 \lt b_2 \lt \dots \lt b_a \le n$.
    268 
    269 Let the distance between two working batteries $b_i$ and $b_{i+1}$ be $b_j-b_i$ if $i \lt a$ and $b_1+n-b_a$ if $i = a$. Note that this matches the length of a circle arc between $b_i$ and $b_{i+1}$ that doesn't contain any other working battery.
    270 
    271 Observe that the sum of the distances between $b_i$ and $b_{i+1}$ for $1 \le i \le a$ (indices taken $\bmod a$) is exactly $n$, since the corresponding circle arcs make up the entire circumference. Since there are $a$ pairs of working batteries, by Pigeonhole Principle there is some distance that is less than or equal to $\left \lfloor \frac{n}{a} \right \rfloor$
    272 
    273 Consequently, the following strategy works: For every $i$ from $1$ to $\left \lfloor \frac{n}{a} \right \rfloor$, and for every $j$ from $1$ to $n$, query batteries $j$ and $j+i \bmod n$ (if $j+i = 0$, query with battery $n$) which is equivalent to querying battery $j$ and the one $i$ positions ahead clockwise.
    274 
    275 The above takes at most
    276 
    277 $n \times \left \lfloor \frac{n}{a} \right \rfloor \le \left \lfloor \frac{n^2}{a} \right \rfloor$
    278 
    279 trials, as desired.
    280 
    281 **Code**
    282 
    283 ```
    284 #include <bits/stdc++.h>
    285 
    286 using namespace std;
    287 
    288 void main_() {
    289     
    290     int n, x;
    291 	cin >> n;
    292 	
    293 	for (int i = 1; i < n; i++)
    294 	    for (int j = 1; j <= n; j++) {
    295 		    
    296                 x = (i+j)%n;
    297                 
    298                 if(x == 0) {
    299                     x = n;
    300                 }
    301                 
    302                 cout << j << " " << x << endl;
    303                 
    304                 int res;
    305                 cin >> res;
    306                 
    307                 if (res) {
    308                     return;
    309                 }
    310         }
    311 }
    312 
    313 int main() {
    314 	
    315 	int t = 1;
    316 	cin >> t;
    317 	while (t--)
    318 		main_();
    319 	
    320 	return 0;
    321 }
    322 ```
    323 
    324 ### [2155E - Мимо и Юю](/contest/2155/problem/E "Codeforces Round 1056 (Div. 2)")
    325 
    326 **Hint 1**
    327 
    328 When $n = 1$, the total number of turns is fixed.
    329 
    330 **Hint 2**
    331 
    332 When $n = 2$, the winning and losing states depend only on the parity of the amount of tokens in each column.
    333 
    334 **Solution**
    335 
    336 For convenience, let's denote with $d_i$ the number of tokens located in column $i$.
    337 
    338 It's worth noting that the game lasts a finite amount of turns because, the array $[ d_m, d_{m-1}, \dots d_1 ]$ becomes lexicographically smaller (strictly) after each turn.
    339 
    340 Note that we can think of each token independently, as tokens are only removed one at a time by the players.
    341 
    342 We first deal with the case $n = 1$. Let $c_i$ be the column where token $i$ is located. We will prove by induction that token $i$ contributes $2^{c_i-2}$ turns to the game whenever $c_i \ge 2$. That is, $2^{c_i-2}$ turns are necessary and sufficient to remove token $i$ and all the tokens it spawns from the board.
    343 
    344 Base case $c_i = 2$: A player moves token $i$ to column $1$. No tokens are added to the board, so $1 = 2^0$ turns are played in total.
    345 
    346 Otherwise, $c_i-2$ tokens will be added to the board after choosing token $i$, one in each of columns $2, 3, \dots {c_i-1}$. By the induction hypothesis, removing these tokens and all the tokens they spawn will take
    347 
    348 $ \sum_{j=2}^{c_i-1} 2^{j-2} = 2^0+2^1+\dots+2^{i-3} = 2^{c_i-2}-1$
    349 
    350 turns. Adding the initial turn to the total, we get $2^{c_i-2}-1+1 = 2^{c_i-2}$ turns in total.
    351 
    352 The answer is equivalent to the parity of the number of turns performed in total, obtained by summing the contribution of turns by each token. Only tokens in column $2$ contribute an odd amount of turns ($2^0 = 1$ turn) while every other token contributes an even amount of turns ($0$ or $2^{j-2}$ turns), so we just need to print $\texttt{Mimo}$ if there is an odd number of tokens on column $2$ or $\texttt{Yuyu}$ if there is an even amount.
    353 
    354 The only other case is when $n \ge 2$. We claim that the second player wins if and only if, for all $i \ge 2$,
    355 
    356 $d_i \equiv 0 \; \bmod 2$
    357 
    358 * If $d_i = 0$ for all $i \ge 2$: The game is automatically a losing state.
    359 * $d_i \equiv 0 \; \bmod 2$ for all $i \ge 2$ turns out to also be a losing state. Any move would cause some $d_j$ (in particular, $j = b_1$) to go from even to odd; thus, the opponent is given a winning game, as we will prove below.
    360 
    361 We claim that $d_j \equiv 1 \; \bmod 2$ for some $j \ge 2$ is a winning state. Denote the maximum of all such $j$ as $j_{max}$. Our objective will be to give the opponent a game which falls under the first or second bullet point ($d_i \equiv 0 \; \bmod 2$ for all $i \ge 2$). If such a thing is always possible, after a finite amount of moves, the state given to the opponent will necessarily be exactly that of the first bullet point (the "minimal" losing state), proving these states are winning.
    362 
    363 By definition of $j_{max}$, $d_i \equiv 0 \; \bmod 2$ for all ($i \gt j_{max}$). Performing a turn with chosen token $c$ in column $j_{max}$ causes $d_{j_{max}}$ to become $0 \bmod 2$. For all columns $i$ ($i \lt j_{max}$) a move that achieves $d_i \equiv 0 \; \bmod 2$ is as follows:
    364 
    365 * If $d_i \equiv 0 \; \bmod 2$: Make sure $2$ tokens are added to column $i$.
    366 * If $d_i \equiv 1 \; \bmod 2$: Make sure $1$ token is added to column $i$.
    367 
    368 Such a move is possible because $n \ge 2$. This is an example of how it could look like:
    369 
    370 ![ ](/predownloaded/5e/99/5e999bc1fa92d1984d5514f0a315188ef34fb31e.png)
    371 
    372 Time complexity: $\mathcal{O}(k)$ or $\mathcal{O}(k\log m)$ depending on implementation.
    373 
    374 **Code**
    375 
    376 ```
    377 #include <bits/stdc++.h>
    378 using namespace std;
    379 using ll = long long;
    380 using vll = vector <ll>;
    381  
    382 void tc () {
    383     ll n, m, k;
    384     cin >> n >> m >> k;
    385     set <ll> st;
    386     for (ll id = 0; id < k; id++) {
    387         ll i, j;
    388         cin >> i >> j;
    389         if (j == 1) continue;
    390         if (n == 1 && j != 2) continue;
    391         if (st.count(j))
    392             st.erase(j);
    393         else
    394             st.insert(j);
    395     }
    396     cout << (st.size() > 0 ? "Mimo" : "Yuyu") << '\n';
    397 }
    398  
    399 int main () {
    400     cin.tie(nullptr) -> sync_with_stdio(false);
    401     ll T; cin >> T; while (T--) { tc(); }
    402     return 0;
    403 }
    404 ```
    405 
    406 ### [2155F - Цветное дерево Хуана](/contest/2155/problem/F "Codeforces Round 1056 (Div. 2)")
    407 
    408 **Hint 1**
    409 
    410 Consider the graph formed by the vertices with color $x$ and the edges between them. What happens if a query contains two vertices in the one of this graph's connected components ("color components")?
    411 
    412 **Hint 2**
    413 
    414 After assigning IDs to each "color component" (for all colors), we can calculate the answer for two vertices by counting the number of components which contain both of them.
    415 
    416 **Hint 3**
    417 
    418 We can precompute the answer for all possible queries containing vertex $x$ with DFS.
    419 
    420 **Hint 4**
    421 
    422 Determining all answers with only one of the two aforementioned methods is very expensive. Is there some way to balance the complexity by using one over the other in certain situations?
    423 
    424 **Solution**
    425 
    426 There are some solutions with square-root complexity with an additional log factor that can pass if optimized enough, but we will present an $\mathcal{O}((n+q+s)\sqrt s)$ solution.
    427 
    428 Let's first transform the problem from calculating the intersection of $C_w$ for all nodes $w$ in the path from $a_i$ to $b_i$ ($\left| C_{a_i} \cap \dots \cap C_{b_i} \right|$) to calculating the intersection of 2 sets: $D_{a_i}$ and $D_{b_i}$. We will calculate $\left|D_{a_i} \cap D_{b_i}\right|$ in average square-root complexity, using the best of 2 algorithms for each type of query.
    429 
    430 First, let's define the sets $D_1, D_2, \dots D_n$. Let a *maximal color component* be a set of vertices, all of which contain some color $x$ in their sets, such that there is no other vertex with color $x$ adjacent to some vertex of the maximal component. We will assign an arbitrary ID to each maximal color component, and $D_u$ will contain the IDs of the maximal color components which node $u$ belongs to.
    431 
    432 Note that $\left| D_u \right| = \left| C_u \right|$. Also note that the answer now is simply $\left|D_{a_i} \cap D_{b_i}\right|$. A possible $\mathcal{O}\left(n+s+k\right)$ algorithm calculating the sets $D_i$ is to maintain $k$ stacks while doing a DFS where, when visiting node $u$, stack $c$ contains the ancestors of node $u$ with color $c$. Checking the top of the stack suffices to know if a new component is created, or inherited from one's parent.
    433 
    434 Here are 2 algorithms which calculate the cardinality of the intersection: One answers a query for a given pair of nodes $a_i$, $b_i$ and runs in $\mathcal{O}\left( |D_{a_i}|+|D_{b_i}| \right)$. The other calculates the answer between a fixed node $u$ and all $n$ nodes in $\mathcal{O}\left( n+s \right)$.
    435 
    436 The first algorithm relies on sorting the sets $D_u$ (stored in lists or arrays), and then using the two-pointers technique to calculate the intersection of two sorted arrays in linear time. The second algorithm roots the tree in $u$ and starts a DFS, where the frequency of all $k$ colors across ancestors is maintained. For every node $v$, it calculates if the frequency of every color in $C_v$ is equal to its depth.
    437 
    438 Let $B$ be a fixed integer. We precompute answers when $|D_u| \ge B$ using the $\mathcal{O}\left( n+s \right)$ algorithm. Otherwise, we use the $\mathcal{O}\left( |D_{a_i}|+|D_{b_i}| \right)$ algorithm for queries in which $|D_{a_i}|, |D_{b_i}| \le B$. The complexity of this approach is $\mathcal{O}\left( qB + (s/B)(n+s) \right)$ because there are at most $s/B$ vertices whose sets have a cardinality greater than $B$. Setting $B$ to be around $\sqrt s$, we get that our procedure runs in $\mathcal{O}\left(q\sqrt s + \sqrt s (n+s) \right) = \mathcal{O}\left( (n+q+s)\sqrt s \right)$.
    439 
    440 Time complexity: $\mathcal{O}\left( (n+q+s)\sqrt s \right)$
    441 
    442 Memory complexity: $\mathcal{O}\left( s + n\sqrt s \right)$
    443 
    444 **Code**
    445 
    446 ```
    447 #include <bits/stdc++.h>
    448 using namespace std;
    449 using ll = long long;
    450 using vll = vector <ll>;
    451  
    452 const ll MAXN = 3E5+16, B = 800;
    453 vll adj[MAXN];
    454 vll cols[MAXN], comps[MAXN];
    455 ll comp_col[MAXN];
    456 ll timer = 1, cur = 1;
    457 ll last[MAXN];
    458 bool active[MAXN];
    459 ll curMap[MAXN];
    460 int preProc[MAXN/B+16][MAXN];
    461  
    462 void dfs1 (ll u, ll par) {
    463     vll th(cols[u].size()), th2(cols[u].size());
    464     comps[u].resize(cols[u].size());
    465     for (ll i = 0; i < cols[u].size(); i++) {
    466         ll c = cols[u][i];
    467         th[i] = last[c];
    468         th2[i] = comp_col[c];
    469         comp_col[c] = (last[c] == par ? comp_col[c] : timer++);
    470         comps[u][i] = comp_col[c];
    471         last[c] = u;
    472     }
    473     for (ll v : adj[u]) {
    474         if (v == par) continue;
    475         dfs1(v, u);
    476     }
    477     for (ll i = 0; i < cols[u].size(); i++) {
    478         ll c = cols[u][i];
    479         last[c] = th[i];
    480         comp_col[c] = th2[i];
    481     }
    482 }
    483  
    484 void tc () {
    485     ll n, k, s, q;
    486     cin >> n >> k >> s >> q;
    487     fill(adj, adj+n, vll({}));
    488     for (ll i = 1; i < n; i++) {
    489         ll u, v;
    490         cin >> u >> v;
    491         u--; v--;
    492         adj[u].push_back(v);
    493         adj[v].push_back(u);
    494     }
    495     timer = 1;
    496     cur = 1;
    497     fill(cols, cols+n, vll({}));
    498     fill(comps, comps+n, vll({}));
    499     fill(comp_col, comp_col+k, -16);
    500     fill(last, last+k, -16);
    501     for (ll i = 0; i < s; i++) {
    502         ll x, c;
    503         cin >> x >> c;
    504         x--; c--;
    505         cols[x].push_back(c);
    506     }
    507     dfs1(0, 0);
    508     for (ll u = 0; u < n; u++) {
    509         sort(comps[u].begin(), comps[u].end());
    510     }
    511     for (ll u = 0; u < n; u++) {
    512         if (cols[u].size() < B) continue;
    513         // >= B
    514         for (ll c : comps[u]) active[c] = true;
    515         for (ll v = 0; v < n; v++) {
    516             preProc[cur][v] = 0;
    517             for (ll c : comps[v]) {
    518                 preProc[cur][v] += active[c];
    519             }
    520         }
    521         for (ll c : comps[u]) active[c] = false;
    522         curMap[u] = cur++;
    523     }
    524     while (q--) {
    525         ll u, v;
    526         cin >> u >> v;
    527         u--; v--;
    528         if (cols[u].size() >= B) {
    529             cout << preProc[curMap[u]][v] << ' ';
    530             continue;
    531         }
    532         if (cols[v].size() >= B) {
    533             cout << preProc[curMap[v]][u] << ' ';
    534             continue;
    535         }
    536         ll ans = 0;
    537         ll p1 = 0;
    538         for (ll p2 = 0; p2 < comps[v].size(); p2++) {
    539             while (p1 < comps[u].size() && comps[u][p1] < comps[v][p2]) p1++;
    540             if (p1 == comps[u].size() || comps[u][p1] != comps[v][p2]) continue;
    541             ans++;
    542         }
    543         cout << ans << ' ';
    544     }
    545     cout << '\n';
    546 }
    547  
    548 int main () {
    549     cin.tie(nullptr) -> sync_with_stdio(false);
    550     ll T; cin >> T; while (T--) { tc(); }
    551     return 0;
    552 }
    553 ```