codeforces-scrape

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

2131.md (21670B)


      1 Source: https://codeforces.com/blog/entry/145439
      2 
      3 I hope you all enjoyed the contest!
      4 
      5 **Rating Predictions**
      6 
      7 | Predictor | A | B | C | D | E | F | G | H |
      8 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
      9 | [AksLolCoding](/profile/AksLolCoding "Master AksLolCoding") | 800 | 900 | 1000 | 1400 | 1500 | 1800 | 1800 | — |
     10 | [ALnQ417](/profile/ALnQ417 "Specialist ALnQ417") | 800 | 900 | 1100 | 1300 | 1500 | 1600 | — | — |
     11 | [bookcat](/profile/bookcat "International Master bookcat") | 800 | 1200 | 1200 | 1500 | 1600 | 1600 | 1600 | 2000 |
     12 | [chromate00](/profile/chromate00 "Expert chromate00") | 800 | 800 | 1000 | 1400 | 1400 | 1800 | 1800 | 2200 |
     13 | [cry](/profile/cry "International Master cry") | 800 | 1000 | 1200 | 1600 | 1700 | 2100 | 2100 | 2400 |
     14 | [Edeeva](/profile/Edeeva "Candidate Master Edeeva") | 800 | 800 | 1000 | 1300 | 1400 | 1600 | 1900 | — |
     15 | [efishel](/profile/efishel "Master efishel") | 800 | 1000 | 1000 | 1500 | 1500 | 1800 | 1900 | 2200 |
     16 | [_Equinox](/profile/_Equinox "Expert _Equinox") | 800 | 800 | 800 | 1200 | 1500 | 1600 | 1800 | — |
     17 | [fatalerror](/profile/fatalerror "Candidate Master fatalerror") | 800 | 1400 | 1200 | 1600 | 1700 | 1900 | 2000 | 2100 |
     18 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 800 | 900 | 1400 | 1400 | 1600 | 1800 | 2500 |
     19 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 800 | 1000 | 1500 | 1600 | 1800 | 1900 | 2400 |
     20 | [Non-origination](/profile/Non-origination "Expert Non-origination") | 800 | 800 | 1000 | 1600 | 1300 | 1600 | 1800 | — |
     21 | [reirugan](/profile/reirugan "Candidate Master reirugan") | 800 | 900 | 1200 | 1500 | 1500 | 1800 | 1800 | — |
     22 | [temporary1](/profile/temporary1 "International Master temporary1") | 800 | 800 | 900 | 1400 | 1300 | 1800 | 1900 | 2200 |
     23 | [white_two](/profile/white_two "Specialist white_two") | 800 | 800 | 1200 | 1400 | 1400 | 1900 | — | — |
     24 
     25 **Rate the contest!**
     26 
     27 **Quality**
     28 
     29 * Excellent contest
     30 * Good contest
     31 * Average contest
     32 * Bad contest
     33 * Horrible contest
     34 
     35 **Difficulty**
     36 
     37 * Trivial contest
     38 * Easy contest
     39 * Average contest
     40 * Hard contest
     41 * Impossible contest
     42 
     43 [2131A - Lever](/contest/2131/problem/A "Codeforces Round 1042 (Div. 3)")
     44 
     45 Idea: [-firefly-](/profile/-firefly- "Master -firefly-")   
     46  Preparation: [-firefly-](/profile/-firefly- "Master -firefly-")   
     47  Analysis: [temporary1](/profile/temporary1 "International Master temporary1")
     48 
     49 **Hint**
     50 
     51 The step $2$ doesn't affect step $1$.
     52 
     53 **Solution**
     54 
     55 Tutorial is loading...
     56 
     57 **Code (Python)**
     58 
     59 ```
     60 import sys
     61 input = lambda: sys.stdin.readline().rstrip()
     62 ii = lambda: int(input())
     63 mii = lambda: map(int, input().split())
     64 lii = lambda: list(mii())
     65 
     66 def solve():
     67     n = ii()
     68     A = lii()
     69     B = lii()
     70     return sum(a - b for a, b in zip(A, B) if a > b) + 1
     71 
     72 for _ in range(ii()):
     73     print(solve())
     74 ```
     75 
     76 **Rate the problem!**
     77 
     78 **Quality**
     79 
     80 * Excellent problem
     81 * Good problem
     82 * Average problem
     83 * Bad problem
     84 * Horrible problem
     85 
     86 **Difficulty**
     87 
     88 * Trivial problem
     89 * Easy problem
     90 * Average problem
     91 * Hard problem
     92 * Impossible problem
     93 
     94 [2131B - Alternating Series](/contest/2131/problem/B "Codeforces Round 1042 (Div. 3)")
     95 
     96 Idea: [-firefly-](/profile/-firefly- "Master -firefly-")   
     97  Preparation: [-firefly-](/profile/-firefly- "Master -firefly-")   
     98  Analysis: [reirugan](/profile/reirugan "Candidate Master reirugan")
     99 
    100 **Hint 1**
    101 
    102 There are no much difference between the series when $n=k$ and $n=k+1$.
    103 
    104 **Hint 2**
    105 
    106 Construct the series from the left to the right greedily.
    107 
    108 **Solution**
    109 
    110 Tutorial is loading...
    111 
    112 **Code (Python)**
    113 
    114 ```
    115 import sys
    116 input = lambda: sys.stdin.readline().rstrip()
    117 ii = lambda: int(input())
    118 mii = lambda: map(int, input().split())
    119 lii = lambda: list(mii())
    120 
    121 def solve():
    122     n = ii()
    123     if n == 1:
    124         return [0]
    125     ans = [-1, 3] * (n // 2)
    126     if n % 2:
    127         ans.append(-1)
    128     else:
    129         ans[-1] = 2
    130     return ans
    131 
    132 for _ in range(ii()):
    133     print(*solve())
    134 ```
    135 
    136 **Rate the problem!**
    137 
    138 **Quality**
    139 
    140 * Excellent problem
    141 * Good problem
    142 * Average problem
    143 * Bad problem
    144 * Horrible problem
    145 
    146 **Difficulty**
    147 
    148 * Trivial problem
    149 * Easy problem
    150 * Average problem
    151 * Hard problem
    152 * Impossible problem
    153 
    154 [2131C - Make it Equal](/contest/2131/problem/C "Codeforces Round 1042 (Div. 3)")
    155 
    156 Idea: [Tobo](/profile/Tobo "International Master Tobo")   
    157  Preparation: [Tobo](/profile/Tobo "International Master Tobo"), [-firefly-](/profile/-firefly- "Master -firefly-"), [Friedrich](/profile/Friedrich "Master Friedrich")   
    158  Analysis: [Tobo](/profile/Tobo "International Master Tobo")
    159 
    160 **Hint**
    161 
    162 Consider the operations modulo $k$.
    163 
    164 **Solution**
    165 
    166 Tutorial is loading...
    167 
    168 **Code (Python)**
    169 
    170 ```
    171 import sys
    172 input = lambda: sys.stdin.readline().rstrip()
    173 ii = lambda: int(input())
    174 mii = lambda: map(int, input().split())
    175 lii = lambda: list(mii())
    176 
    177 from collections import defaultdict
    178 from random import getrandbits
    179 RD = getrandbits(31)
    180 
    181 def solve():
    182     n, k = mii()
    183     A = lii()
    184     B = lii()
    185     cnt = defaultdict(int)
    186     for x in A:
    187         r = x % k
    188         cnt[min(r, k-r) ^ RD] += 1
    189     for x in B:
    190         r = x % k
    191         cnt[min(r, k-r) ^ RD] -= 1
    192     return all(v == 0 for v in cnt.values())
    193 
    194 for _ in range(ii()):
    195     print('YES' if solve() else 'NO')
    196 ```
    197 
    198 **Rate the problem!**
    199 
    200 **Quality**
    201 
    202 * Excellent problem
    203 * Good problem
    204 * Average problem
    205 * Bad problem
    206 * Horrible problem
    207 
    208 **Difficulty**
    209 
    210 * Trivial problem
    211 * Easy problem
    212 * Average problem
    213 * Hard problem
    214 * Impossible problem
    215 
    216 [2131D - Arboris Contractio](/contest/2131/problem/D "Codeforces Round 1042 (Div. 3)")
    217 
    218 Idea: [-firefly-](/profile/-firefly- "Master -firefly-")   
    219  Preparation: [-firefly-](/profile/-firefly- "Master -firefly-")   
    220  Analysis: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__")
    221 
    222 **Hint 1**
    223 
    224 What is the minimum diameter achievable?
    225 
    226 **Hint 2**
    227 
    228 How are leaves significant?
    229 
    230 **Solution**
    231 
    232 Tutorial is loading...
    233 
    234 **Code (Python)**
    235 
    236 ```
    237 import sys
    238 input = lambda: sys.stdin.readline().rstrip()
    239 ii = lambda: int(input())
    240 mii = lambda: map(int, input().split())
    241 lii = lambda: list(mii())
    242 
    243 def solve():
    244     n = ii()
    245     g = [[] for _ in range(n)]
    246     deg = [0] * n
    247     for _ in range(n-1):
    248         u, v = mii()
    249         u -= 1; v -= 1
    250         g[u].append(v)
    251         g[v].append(u)
    252         deg[u] += 1
    253         deg[v] += 1
    254     if n <= 3:
    255         return 0
    256 
    257     c1 = sum(deg[u] == 1 for u in range(n))
    258     mx = max(sum(deg[v] == 1 for v in g[u]) for u in range(n))
    259     return c1 - mx
    260 
    261 for _ in range(ii()):
    262     print(solve())
    263 ```
    264 
    265 **Rate the problem!**
    266 
    267 **Quality**
    268 
    269 * Excellent problem
    270 * Good problem
    271 * Average problem
    272 * Bad problem
    273 * Horrible problem
    274 
    275 **Difficulty**
    276 
    277 * Trivial problem
    278 * Easy problem
    279 * Average problem
    280 * Hard problem
    281 * Impossible problem
    282 
    283 [2131E - Adjacent XOR](/contest/2131/problem/E "Codeforces Round 1042 (Div. 3)")
    284 
    285 Idea: [-firefly-](/profile/-firefly- "Master -firefly-")   
    286  Preparation: [-firefly-](/profile/-firefly- "Master -firefly-")   
    287  Analysis: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__")
    288 
    289 **Solution**
    290 
    291 Tutorial is loading...
    292 
    293 **Code (Python)**
    294 
    295 ```
    296 import sys
    297 input = lambda: sys.stdin.readline().rstrip()
    298 ii = lambda: int(input())
    299 mii = lambda: map(int, input().split())
    300 lii = lambda: list(mii())
    301 
    302 def solve():
    303     n = ii()
    304     A = lii()
    305     B = lii()
    306     if A[-1] != B[-1]:
    307         return False
    308     for i in range(n-2, -1, -1):
    309         if A[i] != B[i] and A[i] ^ A[i+1] != B[i] and A[i] ^ B[i+1] != B[i]:
    310             return False
    311     return True
    312 
    313 for _ in range(ii()):
    314     print('YES' if solve() else 'NO')
    315 ```
    316 
    317 **Rate the problem!**
    318 
    319 **Quality**
    320 
    321 * Excellent problem
    322 * Good problem
    323 * Average problem
    324 * Bad problem
    325 * Horrible problem
    326 
    327 **Difficulty**
    328 
    329 * Trivial problem
    330 * Easy problem
    331 * Average problem
    332 * Hard problem
    333 * Impossible problem
    334 
    335 [2131F - Unjust Binary Life](/contest/2131/problem/F "Codeforces Round 1042 (Div. 3)")
    336 
    337 Idea: [efishel](/profile/efishel "Master efishel"), [__baozii__](/profile/__baozii__ "Grandmaster __baozii__")   
    338  Preparation: [-firefly-](/profile/-firefly- "Master -firefly-")   
    339  Analysis: [temporary1](/profile/temporary1 "International Master temporary1"), [reirugan](/profile/reirugan "Candidate Master reirugan")
    340 
    341 **Hint 1**
    342 
    343 The grid possesses a significant property. Try to generate some grids with random $a$ and $b$, and understand the distribution of $0$'s and $1$'s.
    344 
    345 **Hint 2**
    346 
    347 For each point $(x, y)$, you can derive the answer formula like $\min(f(x,y), g(x,y))$. Note that $\displaystyle\min(f,g)=\frac{f+g}{2}-\frac{|f-g|}{2}$
    348 
    349 **Solution**
    350 
    351 Tutorial is loading...
    352 
    353 **Code (C++)**
    354 
    355 ```
    356 #include <bits/stdc++.h>
    357 using namespace std;
    358 
    359 #define f first
    360 #define s second
    361 #define ll long long
    362 #define pii pair<int,int>
    363 #define pli pair<ll,int>
    364 #define pll pair<ll,ll>
    365 #define tiii tuple<int,int,int>
    366 #define tiiii tuple<int,int,int,int>
    367 #define pb push_back
    368 #define eb emplace_back
    369 #define emp emplace
    370 #define mkp make_pair
    371 #define mkt make_tuple
    372 #define vctr vector
    373 #define arr array
    374 #define all(x) x.begin(), x.end()
    375 #define amin(a,b) a = min(a,b)
    376 #define amax(a,b) a = max(a,b)
    377 #define brick(x) cout << #x << " = " << (x) << " | "
    378 #define dbg(x) cout << #x << " = " << (x) << '\n'
    379 #define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
    380 #define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
    381 #define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
    382 mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
    383 int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
    384 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
    385 
    386 const int MOD = 1e9+7; // 998244353;
    387 
    388 int a[200005];
    389 int b[200005];
    390 int c[200005][2];
    391 int d[200005][2];
    392 ll pf[400005][2];
    393 int cnt[400005];
    394 
    395 int main() {
    396 	ios_base::sync_with_stdio(false);
    397 	cin.tie(NULL);
    398 	int tt;
    399 	cin >> tt;
    400 	while (tt--) {
    401 		int n;
    402 		cin >> n;
    403 		string t;
    404 		cin >> t;
    405 		for (int i = 1; i <= n; ++i) {
    406 			a[i] = (t[i-1] == '1');
    407 		}
    408 		cin >> t;
    409 		for (int i = 1; i <= n; ++i) {
    410 			b[i] = (t[i-1] == '1');
    411 		}
    412 		const int o = n;
    413 		for (int i = 0; i <= 2*n; ++i) {
    414 			pf[i][0] = 0;
    415 			pf[i][1] = 0;
    416 			cnt[i] = 0;
    417 		}
    418 		for (int i = 1; i <= n; ++i) {
    419 			c[i][0] = c[i-1][0]+(a[i] == 0);
    420 			c[i][1] = c[i-1][1]+(a[i] == 1);
    421 			pf[o+c[i][0]-c[i][1]][0] += c[i][0];
    422 			pf[o+c[i][0]-c[i][1]][1] += c[i][1];
    423 			cnt[o+c[i][0]-c[i][1]] += 1;
    424 		}
    425 		for (int i = 1; i <= 2*n; ++i) {
    426 			pf[i][0] += pf[i-1][0];
    427 			pf[i][1] += pf[i-1][1];
    428 			cnt[i] += cnt[i-1];
    429 		}
    430 		for (int i = 1; i <= n; ++i) {
    431 			d[i][0] = d[i-1][0]+(b[i] == 0);
    432 			d[i][1] = d[i-1][1]+(b[i] == 1);
    433 		}
    434 		ll ans = 0;
    435 		for (int i = 1; i <= n; ++i) {
    436 			int z = d[i][1]-d[i][0];
    437 			// 0 worth it when delta <= z
    438 			ans += d[i][0]*(ll)cnt[o+z]+pf[o+z][0];
    439 			ans += d[i][1]*(ll)(n-cnt[o+z])+pf[2*n][1]-pf[o+z][1];
    440 		}
    441 		cout << ans << '\n';
    442 	}
    443 	return 0;
    444 }
    445 ```
    446 
    447 **Rate the problem!**
    448 
    449 **Quality**
    450 
    451 * Excellent problem
    452 * Good problem
    453 * Average problem
    454 * Bad problem
    455 * Horrible problem
    456 
    457 **Difficulty**
    458 
    459 * Trivial problem
    460 * Easy problem
    461 * Average problem
    462 * Hard problem
    463 * Impossible problem
    464 
    465 [2131G - Wafu!](/contest/2131/problem/G "Codeforces Round 1042 (Div. 3)")
    466 
    467 Idea: [-firefly-](/profile/-firefly- "Master -firefly-")   
    468  Preparation: [-firefly-](/profile/-firefly- "Master -firefly-")   
    469  Analysis: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__")
    470 
    471 **Hint 1**
    472 
    473 For a set $S$, how many operations are required to transform $S$ into $S \setminus {\min(S)}$?
    474 
    475 **Hint 2**
    476 
    477 $S$ can be represented as a binary number (though very large).
    478 
    479 **Hint 3**
    480 
    481 How to calculate the answer when elements in $S$ are very large?
    482 
    483 **Solution**
    484 
    485 Tutorial is loading...
    486 
    487 **Code (Python)**
    488 
    489 ```
    490 MOD = 10 ** 9 + 7
    491 
    492 dp = [0] * 31
    493 dp[0] = 1
    494 for i in range(1, 31):
    495     dp[i] = i + 1
    496     for j in range(i):
    497         dp[i] = dp[i] * dp[j] % MOD
    498 
    499 def dfs(v, k):
    500     if k == 0:
    501         return 1
    502     ans = v + 1
    503     v = min(v - 1, 30)
    504     k -= 1
    505     for j in range(v + 1):
    506         if k >= 1 << j:
    507             ans = ans * dp[j] % MOD
    508             k -= 1 << j
    509         else:
    510             ans = ans * dfs(j, k) % MOD
    511             break
    512     return ans
    513 
    514 for _ in range(int(input())):
    515     n, k = map(int, input().split())
    516     s = list(map(int, input().split()))
    517     for i in range(n):
    518         s[i] -= 1
    519     s.sort()
    520     ans = 1
    521     for v in s:
    522         if v <= 30 and k >= 1 << v:
    523             k -= 1 << v
    524             ans = ans * dp[v] % MOD
    525         else:
    526             ans = ans * dfs(v, k) % MOD
    527             break
    528     print(ans)
    529 ```
    530 
    531 **Rate the problem!**
    532 
    533 **Quality**
    534 
    535 * Excellent problem
    536 * Good problem
    537 * Average problem
    538 * Bad problem
    539 * Horrible problem
    540 
    541 **Difficulty**
    542 
    543 * Trivial problem
    544 * Easy problem
    545 * Average problem
    546 * Hard problem
    547 * Impossible problem
    548 
    549 [2131H - Sea, You & copriMe](/contest/2131/problem/H "Codeforces Round 1042 (Div. 3)")
    550 
    551 Idea: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__"), [-firefly-](/profile/-firefly- "Master -firefly-")   
    552  Preparation: [-firefly-](/profile/-firefly- "Master -firefly-")   
    553  Analysis: [-firefly-](/profile/-firefly- "Master -firefly-")
    554 
    555 **Hint 1**
    556 
    557 Let's consider an easier problem: how do we find one coprime pair from $a$?
    558 
    559 **Step 1**
    560 
    561 If there exists one coprime pair, it means there exists an $i$ such that
    562 
    563 $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] - [a_i = 1] \gt 0$
    564 
    565 In other words, there are at least one other indices $j$ such that $\gcd(a_i, a_j)=1$.
    566 
    567 Therefore, we strengthen the problem that we need to find $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1]$ for each $i$. Here, we introduce two ways to solve the formula.
    568 
    569 In the following discussion, we denote $f(d)$ to be the count of elements in $a$ divisible by $d$. We can precompute $f(1), f(2), \dots, f(m)$ in $O(m\log m)$ time using harmonic trick.
    570 
    571 **Principle of Inclusion-Exclusion (PIE)**
    572 
    573 For each $a_i$, find the set of distinct prime factors of $a_i$. Let's call this set $P_i$. For each prime factor $p_k \in P_i$, let $S_k$ be the set of elements in the array $a$ that are divisible by $p_k$.
    574 
    575 Any number that is NOT coprime to $a_i$ must share at least one prime factor with $a_i$, so it must belongs to the set union $S_1 \cup S_2 \cup \dots \cup S_k$. By PIE we can calculate the size of the union:
    576 
    577 $\displaystyle|S_1 \cup S_2 \cup \dots \cup S_k| = \sum_{r} |S_r| - \sum_{r \lt s} |S_r \cap S_s| + \sum_{r \lt s \lt t} |S_r \cap S_s \cap S_t| - \cdots$
    578 
    579 Here:
    580 
    581 * $|S_r|$ is the count of elements in $a$ divisible by $p_r$, which is $f(p_r)$.
    582 * $|S_r \cap S_s|$ is the count of elements in $a$ divisible by both $p_r$ and $p_s$, that is, divisible by $p_rp_s$, which is $f(p_rp_s)$.
    583 * Similarly, $|S_r \cap S_s \cap S_t|$ is $f(p_rp_sp_t)$.
    584 
    585 Since $f(d)$ has been precomputed, we can compute $|S_1 \cup S_2 \cup \dots \cup S_k|$ for each $i$ in $O(2^{|P_i|})$ time. Because $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 9699690 \gt 10^6$, the size of $P_i$ won't exceed $7$. Therefore, the operation number is roughly $2^7 \cdot n \le 3 \cdot 10^7$, which is acceptable.
    586 
    587 After finding the count of elements that is NOT coprime to $a_i$, we can then easily obtain $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1]$ by subtraction.
    588 
    589 **Mobius Inversion**
    590 
    591 Another advanced approach to find the result is Mobius inversion. We will assume that you know the definition and property of mobius function $\mu(n)$ in the following discussion.
    592 
    593 Since we know that $\displaystyle[\gcd(x, y) = 1] = \sum_{d|\gcd(x, y)}\mu(d)$, we can expand the orginal formula as:
    594 
    595 $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] = \sum_{j=1}^{n}\sum_{d|\gcd(a_i, a_j)}\mu(d)$
    596 
    597 Let's swap the order of summation and get
    598 
    599 $\displaystyle\sum_{d=1}^{m}\mu(d)\left(\sum_{j=1}^{n}[d|\gcd(a_i,a_j)]\right)$
    600 
    601 Because $d | \gcd(a_i, a_j)$ is equivalent to $d|a_i$ and $d|a_j$, we can simplify the formula to
    602 
    603 $\displaystyle\sum_{d|a_i}\mu(d)\left(\sum_{j=1}^{n}[d|a_j]\right) = \sum_{d|a_i}\mu(d)f(d)$
    604 
    605 Thus, we can enumerate the divisors of $a_i$ for each $i$ and compute the summation above by brute force, which yields a $O(n\sqrt{m})$ or $O(nd(n))$ time.
    606 
    607 **Hint 2**
    608 
    609 Let's build a graph $G$ where vertex $i$ and $j$ has an undirected edge if and only if $\gcd(a_i, a_j) = 1$. The problem becomes finding a match of size $2$ in the graph. However, we only has each vertex's degrees based on the discussion above. How do we find the match only based on degrees?
    610 
    611 **Step 2**
    612 
    613 We use a greedy approach to obtain the match of size $2$. Let's say $G$ has at least one edge.
    614 
    615 1. Choose a vertex $u$ with the maximum degree.
    616 2. From all vertices that is connected to $u$, pick a vertex $v$ with the minimum degree.
    617 3. Remove vertices $u$ and $v$ and their associated edges from $G$ to get a new graph $G^\prime$.
    618 4. If there are at least one remaining edge in $G^\prime$, $G$ has a match of size $2$ that contains $(u, v)$ and the remaining edge. Otherwise, it doesn't have a match of size $2$.
    619 
    620 **Proof of correctness**
    621 
    622 We will prove that if $G^\prime$ contains no edges, $G$ doesn't have a match of size $2$.
    623 
    624 Because $G^\prime$ has no edge, all of the vertices that is not isolated in $G$ connect to $u$, $v$ or both. It means $G$ has only one connected component that contains more than two vertices. To make disucssion easier, we will use $G$ to refer to $G$'s major connect component. That means all of the vertices other than $u$ and $v$ have a degree of $1$ or $2$ in $G$.
    625 
    626 1. If all vertices other than $u$ and $v$ have a degree of $1$. If at least one vertex is connected to $u$, the minimum degree that $u$'s connected vertices becomes $1$. Since the algorithm choose $v$ with the minimum degree, $v$ also has a degree of $1$, so all vertices are connected to $u$. In this case, $G$ is a star-shaped tree, which doesn't have a match of size $2$ for obvious reason. On the other hand, if all vertices are connected to $v$, the degree of $v$ is greater than $u$, which is impossible become the degree of $u$ is maximum.
    627 2. If exactly one vertex other than $u$ and $v$ has a degree of $2$, it must connect to both $u$ and $v$. Similar to the discussion above, we can prove that no other vertex can be connected to either $u$ or $v$. In this case, $G$ is a three-vertex loop, or $K_3$, which doesn't have a match of size $2$.
    628 3. If more than two vertices other than $u$ and $v$ have a degree of $2$, it means $v$ has a degree of more than $3$. Let's denote a vertex that connects to both $u$ and $v$ as $w$, then $\mathrm{deg}(w) = 2 \lt 3 \le \mathrm{deg}(v)$. Because $w$ is also connected to $u$, it contradicts to the step $2$ of the algorithm.
    629 
    630 For our problem, for each $i$, the degree is $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] - [a_i = 1]$. We can then brute force to find the first edge, remove it, and then try to find the second edge.
    631 
    632 **Code (C++)**
    633 
    634 ```
    635 #include <bits/stdc++.h>
    636 using i64 = long long;
    637 constexpr int V = 1e6 + 10;
    638 
    639 std::array<int, V> mu, comp;
    640 std::vector<int> primes;
    641 
    642 void solve() {
    643     int n, m = 0;
    644     std::cin >> n;
    645     std::vector<int> a(n);
    646     for (int i = 0; i < n; ++i) {
    647         std::cin >> a[i];
    648         m = std::max(m, a[i]);
    649     }
    650     std::vector<int> mul(m+1), deg(n), mp(m+1);
    651     for (int i = 0; i < n; ++i) {
    652         mp[a[i]]++;
    653     }
    654     for (int j = 1; j <= m; ++j) {
    655         for (int x = j; x <= m; x += j) {
    656             mul[j] += mp[x];
    657         }
    658     }
    659     for (int i = 0; i < n; ++i) {
    660         for (int j = 1; j * j <= a[i]; ++j) {
    661             if (a[i] % j == 0) {
    662                 deg[i] += mu[j] * mul[j];
    663                 if (j * j < a[i]) {
    664                     deg[i] += mu[a[i] / j] * mul[a[i] / j];
    665                 }
    666             }
    667         }
    668         if (a[i] == 1) --deg[i];
    669     }
    670     std::array<int, 4> ans;
    671     int u = 0, v = 0, mind = INT32_MAX;
    672     for (int i = 1; i < n; ++i) {
    673         if (deg[i] > deg[u]) {
    674             u = i;
    675         }
    676     }
    677     if (!deg[u]) {
    678         std::cout << "0\n";
    679         return;
    680     }
    681     deg[u] = 0;
    682     for (int i = 0; i < n; ++i) {
    683         if (i == u) continue;
    684         if (std::gcd(a[i], a[u]) == 1) {
    685             --deg[i];
    686             if (mind > deg[i]) {
    687                 mind = deg[i];
    688                 v = i;
    689             }
    690         }
    691     }
    692     ans[0] = u;
    693     ans[1] = v;
    694     deg[v] = 0;
    695     for (int i = 0; i < n; ++i) {
    696         if (i == u || i == v) continue;
    697         if (std::gcd(a[i], a[v]) == 1) {
    698             --deg[i];
    699         }
    700     }
    701     u = 0;
    702     for (int i = 1; i < n; ++i) {
    703         if (deg[i] > deg[u]) {
    704             u = i;
    705         }
    706     }
    707     if (!deg[u]) {
    708         std::cout << "0\n";
    709         return;
    710     }
    711     v = -1;
    712     for (int i = 0; i < n; ++i) {
    713         if (i == u || !deg[i]) continue;
    714         if (std::gcd(a[i], a[u]) == 1) {
    715             v = i;
    716             break;
    717         }
    718     }
    719     assert(v >= 0);
    720     ans[2] = u; ans[3] = v;
    721     for (int i = 0; i < 4; ++i) {
    722         std::cout << ans[i] + 1 << " \n"[i == 3];
    723     }
    724 }
    725 
    726 int main() {
    727     std::cin.tie(nullptr)->sync_with_stdio(false);
    728     int T = 1;
    729     std::cin >> T;
    730     mu[1] = 1;
    731     for (int i = 2; i < V; ++i) {
    732         if (!comp[i]) {
    733             primes.emplace_back(i);
    734             mu[i] = -1;
    735         }
    736         for (auto p: primes) {
    737             int q = i * p;
    738             if (q >= V) break;
    739             comp[q] = true;
    740             if (i % p == 0) {
    741                 mu[q] = 0;
    742                 break;
    743             } else {
    744                 mu[q] = -mu[i];
    745             }
    746         }
    747     }
    748     while (T--) solve();
    749     return 0;
    750 }
    751 ```
    752 
    753 **Rate the problem!**
    754 
    755 **Quality**
    756 
    757 * Excellent problem
    758 * Good problem
    759 * Average problem
    760 * Bad problem
    761 * Horrible problem
    762 
    763 **Difficulty**
    764 
    765 * Trivial problem
    766 * Easy problem
    767 * Average problem
    768 * Hard problem
    769 * Impossible problem