2196.md (19346B)
1 Source: https://codeforces.com/blog/entry/151052 2 3 Thank you for participating! We hope you enjoyed the problems. 4 5 [2197A - Friendly Numbers](/contest/2197/problem/A "Codeforces Round 1079 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 t = int(input()) 15 for tt in range(t): 16 n = int(input()) 17 ans = 0 18 19 def dig_sum(n): 20 s = str(n) 21 sum = 0 22 for j in s: 23 sum += ord(j) - ord('0') 24 return sum 25 26 for i in range(n, n + 200): 27 if i - dig_sum(i) == n: 28 ans += 1 29 print(ans) 30 ``` 31 32 [2197B - Array and Permutation](/contest/2197/problem/B "Codeforces Round 1079 (Div. 2)") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution** 39 40 ``` 41 #include <bits/stdc++.h> 42 43 #define all(a) a.begin(), a.end() 44 #define rall(a) a.rbegin(), a.rend() 45 #define len(a) int(a.size()) 46 using ll = long long; 47 using ull = unsigned long long; 48 using ld = long double; 49 50 using namespace std; 51 52 const int mod = 998244353; 53 54 const int N = 1e6 + 228; 55 56 pair<int, int> zero = {-1, N}; 57 58 59 void solve() { 60 int n; 61 cin >> n; 62 map<int, int> pos; 63 for (int i = 0; i < n; ++i) { 64 int a; 65 cin >> a; 66 pos[a] = i; 67 } 68 int lst = -1; 69 vector<int> b(n); 70 for (int i = 0; i < n; ++i) cin >> b[i]; 71 for (int i = 0; i < n; ++i) { 72 if (lst > pos[b[i]]) { 73 cout << "NO\n"; 74 return; 75 } 76 lst = pos[b[i]]; 77 } 78 cout << "YES\n"; 79 } 80 81 int main(int argc, char* argv[]) { 82 ios_base::sync_with_stdio(0); 83 cin.tie(0); 84 85 int t = 1; 86 cin >> t; 87 while (t--) solve(); 88 } 89 ``` 90 91 [2196A - Game with a Fraction](/contest/2196/problem/A "Codeforces Round 1079 (Div. 1)") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution** 98 99 ``` 100 #include<bits/stdc++.h> 101 using namespace std; 102 103 #define int long long 104 105 void solve(){ 106 int p, q; 107 cin >> p >> q; 108 if (p < q && min(p / 2, q / 3) >= q - p){ 109 cout << "Bob\n"; 110 } 111 else{ 112 cout << "Alice\n"; 113 } 114 } 115 116 signed main() 117 { 118 #ifdef FELIX 119 auto _clock_start = chrono::high_resolution_clock::now(); 120 #endif 121 ios_base::sync_with_stdio(false); 122 cin.tie(0); 123 cout.tie(0); 124 125 int t = 1; 126 cin >> t; 127 while(t--){ 128 solve(); 129 } 130 131 #ifdef FELIX 132 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 133 chrono::high_resolution_clock::now() 134 - _clock_start).count() << "ms." << endl; 135 #endif 136 return 0; 137 } 138 ``` 139 140 [2196B - Another Problem about Beautiful Pairs](/contest/2196/problem/B "Codeforces Round 1079 (Div. 1)") 141 142 **Tutorial** 143 144 Tutorial is loading... 145 146 **Solution** 147 148 ``` 149 #include <bits/stdc++.h> 150 151 using namespace std; 152 153 #define int long long 154 155 const int SQ = 500; 156 157 void solve(){ 158 int n; 159 cin >> n; 160 vector<int> a(n); 161 for (int i = 0; i < n; i++){ 162 cin >> a[i]; 163 } 164 165 int ans = 0; 166 167 for (int i = 0; i < n; i++){ 168 if (a[i] >= SQ){ 169 for (int j = 1; i + a[i] * j < n; j++){ 170 if (a[i + a[i] * j] == j){ 171 ans++; 172 } 173 } 174 for (int j = 1; i - a[i] * j >= 0; j++){ 175 if (a[i - a[i] * j] == j){ 176 ans++; 177 } 178 } 179 } 180 else{ 181 for (int j = 1; i + a[i] * j < n && j < SQ; j++){ 182 if (a[i + a[i] * j] == j){ 183 ans++; 184 } 185 } 186 } 187 } 188 189 cout << ans << '\n'; 190 } 191 192 signed main() 193 { 194 #ifdef FELIX 195 auto _clock_start = chrono::high_resolution_clock::now(); 196 #endif 197 ios_base::sync_with_stdio(false); 198 cin.tie(0); 199 cout.tie(0); 200 201 int t = 1; 202 cin >> t; 203 while(t--){ 204 solve(); 205 } 206 207 #ifdef FELIX 208 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 209 chrono::high_resolution_clock::now() 210 - _clock_start).count() << "ms." << endl; 211 #endif 212 return 0; 213 } 214 ``` 215 216 [2196C1 - Interactive Graph (Simple Version)](/contest/2196/problem/C1 "Codeforces Round 1079 (Div. 1)") 217 218 **Tutorial** 219 220 Tutorial is loading... 221 222 **Solution** 223 224 ``` 225 #include<bits/stdc++.h> 226 using namespace std; 227 228 #define int long long 229 230 const int INF = 1'000'000'007; 231 232 vector<int> ask(int k){ 233 cout << "? " << k << endl; 234 int l; 235 cin >> l; 236 if (l == -1){ 237 exit(0); 238 } 239 vector<int> res(l); 240 for (int i = 0; i < l; i++){ 241 cin >> res[i]; 242 } 243 return res; 244 } 245 246 void solve(){ 247 int n; 248 cin >> n; 249 250 vector<pair<int, int>> edges; 251 252 for (int i = 0; i < n; i++){ 253 int prev = -1; 254 while(1){ 255 int l = 1, r = (1 << 30); 256 while(l <= r){ 257 int m = l + (r - l) / 2; 258 auto path = ask(m); 259 if (!path.empty() && path[0] < i + 1){ 260 l = m + 1; 261 continue; 262 } 263 if (path.empty() || path[0] > i + 1 || (path.size() > 1 && path[1] > prev)){ 264 r = m - 1; 265 } 266 else{ 267 l = m + 1; 268 } 269 } 270 271 auto path = ask(l); 272 if (path.size() > 1){ 273 edges.emplace_back(path[0], path[1]); 274 prev = path[1]; 275 } 276 else{ 277 break; 278 } 279 } 280 } 281 282 cout << "! " << edges.size() << endl; 283 for (auto [u, v] : edges){ 284 cout << u << ' ' << v << endl; 285 } 286 } 287 288 signed main() 289 { 290 #ifdef FELIX 291 auto _clock_start = chrono::high_resolution_clock::now(); 292 #endif 293 ios_base::sync_with_stdio(false); 294 cin.tie(0); 295 cout.tie(0); 296 297 int t = 1; 298 cin >> t; 299 while(t--){ 300 solve(); 301 } 302 303 #ifdef FELIX 304 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 305 chrono::high_resolution_clock::now() 306 - _clock_start).count() << "ms." << endl; 307 #endif 308 return 0; 309 } 310 ``` 311 312 [2196C2 - Interactive Graph (Hard Version)](/contest/2196/problem/C2 "Codeforces Round 1079 (Div. 1)") 313 314 **Tutorial** 315 316 Tutorial is loading... 317 318 **Solution** 319 320 ``` 321 #include<bits/stdc++.h> 322 323 using namespace std; 324 325 vector<int> ask(int k){ 326 cout << "? " << k << endl; 327 int cnt; 328 cin >> cnt; 329 vector<int> res(cnt); 330 for (int i = 0; i < cnt; i++){ 331 cin >> res[i]; 332 res[i]--; 333 } 334 return res; 335 } 336 337 void solve(){ 338 int n; 339 cin >> n; 340 341 int m = 0; 342 vector<vector<int>> g(n); 343 vector<int> cnt(n, -1); 344 345 function<void(int)> calc = [&](int v){ 346 if (cnt[v] != -1){ 347 return; 348 } 349 cnt[v] = 1; 350 for (int to : g[v]){ 351 calc(to); 352 cnt[v] += cnt[to]; 353 } 354 }; 355 356 vector<int> prev = {0}; 357 int k = 2; 358 359 while(1){ 360 auto cur = ask(k); 361 if (cur.size() == 0){ 362 break; 363 } 364 int com_pref = 0; 365 for (int i = 0; i < min(prev.size(), cur.size()); i++){ 366 if (prev[i] != cur[i]){ 367 break; 368 } 369 com_pref++; 370 } 371 if (prev.size() > com_pref){ 372 calc(prev[com_pref]); 373 } 374 375 if (com_pref > 0){ 376 g[cur[com_pref - 1]].push_back(cur[com_pref]); 377 m++; 378 } 379 if (cnt[cur[com_pref]] == -1){ 380 k++; 381 } 382 else{ 383 k += cnt[cur[com_pref]]; 384 } 385 prev = cur; 386 } 387 388 cout << "! " << m << endl; 389 for (int i = 0; i < n; i++){ 390 for (int to : g[i]){ 391 cout << i + 1 << ' ' << to + 1 << endl; 392 } 393 } 394 } 395 396 signed main() 397 { 398 #ifdef FELIX 399 auto _clock_start = chrono::high_resolution_clock::now(); 400 #endif 401 ios_base::sync_with_stdio(false); 402 cin.tie(0); 403 cout.tie(0); 404 405 int tests = 1; 406 cin >> tests; 407 for (int test = 0; test < tests; test++){ 408 solve(); 409 } 410 #ifdef FELIX 411 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 412 chrono::high_resolution_clock::now() 413 - _clock_start).count() << "ms." << endl; 414 #endif 415 return 0; 416 } 417 ``` 418 419 [2196D - Double Bracket Sequence](/contest/2196/problem/D "Codeforces Round 1079 (Div. 1)") 420 421 **Tutorial** 422 423 Tutorial is loading... 424 425 **Solution** 426 427 ``` 428 #include<bits/stdc++.h> 429 using namespace std; 430 431 #define int long long 432 433 const int INF = 1'000'000'007; 434 435 void solve(){ 436 int n; 437 cin >> n; 438 string s; 439 cin >> s; 440 441 vector<int> stay(n); 442 443 auto delete_cbs = [&](char open, char close){ 444 vector<int> st; 445 for (int i = 0; i < n; i++){ 446 if (s[i] == close){ 447 if (!st.empty() && s[st.back()] == open){ 448 st.pop_back(); 449 } 450 else{ 451 st.push_back(i); 452 } 453 } 454 else if (s[i] == open){ 455 st.push_back(i); 456 } 457 } 458 for (int x : st){ 459 stay[x] = 1; 460 } 461 }; 462 463 delete_cbs('(', ')'); 464 delete_cbs('[', ']'); 465 466 int last_open = 0; 467 int cnt_open = 0, cnt_close = 0; 468 int ans = 1; 469 470 for (int i = 0; i < n; i++){ 471 if (!stay[i]){ 472 continue; 473 } 474 if (s[i] == '(' || s[i] == '['){ 475 cnt_open++; 476 last_open = 1; 477 } 478 else{ 479 cnt_close++; 480 if (last_open){ 481 ans = 0; 482 } 483 last_open = 0; 484 } 485 } 486 if (cnt_open % 2 == 0 || cnt_close % 2 == 0){ 487 ans = 0; 488 } 489 ans += (cnt_open + cnt_close) / 2; 490 cout << ans << '\n'; 491 } 492 493 signed main() 494 { 495 #ifdef FELIX 496 auto _clock_start = chrono::high_resolution_clock::now(); 497 #endif 498 ios_base::sync_with_stdio(false); 499 cin.tie(0); 500 cout.tie(0); 501 502 int t = 1; 503 cin >> t; 504 while(t--){ 505 solve(); 506 } 507 508 #ifdef FELIX 509 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 510 chrono::high_resolution_clock::now() 511 - _clock_start).count() << "ms." << endl; 512 #endif 513 return 0; 514 } 515 ``` 516 517 [2196E1 - Fuzzy Concatenation (Easy Version)](/contest/2196/problem/E1 "Codeforces Round 1079 (Div. 1)") 518 519 **Tutorial** 520 521 Tutorial is loading... 522 523 [2196E2 - Fuzzy Concatenation (Hard version)](/contest/2196/problem/E2 "Codeforces Round 1079 (Div. 1)") 524 525 **Tutorial** 526 527 Tutorial is loading... 528 529 **Solution** 530 531 ``` 532 #include <bits/stdc++.h> 533 534 using namespace std; 535 536 template <typename T> 537 struct SparseTable{ 538 int n, r; 539 vector<vector<T>> t; 540 void build(vector<T> &a) { 541 n = a.size(); 542 r = 32 - __builtin_clz(n); 543 t.resize(r, vector<T>(n + 1)); 544 for(int i = 1; i <= n; ++i) t[0][i] = a[i - 1]; 545 for(int k = 1; k < r; ++k) { 546 for(int i = 1; i + (1 << k) - 1 <= n; ++i) { 547 t[k][i] = f(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]); 548 } 549 } 550 } 551 552 T query(int l, int r) { 553 int k = 31 - __builtin_clz(r - l + 1); 554 return f(t[k][l], t[k][r - (1 << k) + 1]); 555 } 556 557 inline T f(T x, T y){ 558 return min(x, y); 559 } 560 }; 561 562 struct SuffixArray{ 563 int n; 564 vector<int> sa; 565 vector<int> lcp; 566 567 vector<int> _s; 568 vector<int> _inv_sa; 569 SparseTable<int> _st_lcp; 570 571 SuffixArray(){} 572 573 void build(const string& s){ 574 _s.assign(s.size(), 0); 575 for (int i = 0; i < s.size(); i++){ 576 _s[i] = s[i]; 577 } 578 _build(_s); 579 _build_lcp_array(); 580 _st_lcp.build(lcp); 581 } 582 583 void build(const vector<int>& s){ 584 _s.assign(s.size(), 0); 585 for (int i = 0; i < s.size(); i++){ 586 _s[i] = s[i]; 587 } 588 _build(_s); 589 _build_lcp_array(); 590 _st_lcp.build(lcp); 591 } 592 593 void _build(const vector<int>& s){ 594 map<int, int> mp; 595 for (int ch : s){ 596 mp[ch] = 0; 597 } 598 int cc = 1; 599 for (auto& [key, val]: mp){ 600 val = cc++; 601 } 602 603 n = s.size() + 1; 604 vector<int> c(n); 605 sa.assign(n, 0); 606 607 for (int i = 0; i < s.size(); i++){ 608 c[i] = mp[s[i]]; 609 sa[i] = i; 610 } 611 c[n - 1] = 0; 612 sa[n - 1] = n - 1; 613 614 for (int i = 1; (i >> 1) < n; i <<= 1){ 615 if (i != 1){ 616 for (int j = 0; j < n; j++){ 617 sa[j] = (sa[j] - (i >> 1) + n) % n; 618 } 619 } 620 vector<int> cnt(n); 621 for (int j = 0; j < n; j++){ 622 cnt[c[sa[j]]]++; 623 } 624 int su = 0; 625 for (int j = 0; j < n; j++){ 626 su += cnt[j]; 627 cnt[j] = su - cnt[j]; 628 } 629 vector<int> new_sa(n); 630 for (int j = 0; j < n; j++){ 631 new_sa[cnt[c[sa[j]]]++] = sa[j]; 632 } 633 sa.swap(new_sa); 634 635 if (i != 1){ 636 vector<int> new_c(n); 637 new_c[sa[0]] = 0; 638 for (int j = 1; j < n; j++){ 639 if (c[sa[j]] > c[sa[j - 1]] || c[(sa[j] + (i >> 1)) % n] > c[(sa[j - 1] + (i >> 1)) % n]){ 640 new_c[sa[j]] = new_c[sa[j - 1]] + 1; 641 } 642 else{ 643 new_c[sa[j]] = new_c[sa[j - 1]]; 644 } 645 } 646 c.swap(new_c); 647 } 648 } 649 } 650 651 void _build_lcp_array(){ 652 lcp.assign(n - 1, 0); 653 _inv_sa.assign(n, 0); 654 for (int i = 0; i < n; i++){ 655 _inv_sa[sa[i]] = i; 656 } 657 for (int i = 0; i < n; i++){ 658 if (_inv_sa[i] == n - 1){ 659 continue; 660 } 661 lcp[_inv_sa[i]] = 0; 662 if (i > 0 && _inv_sa[i - 1] != n - 1){ 663 lcp[_inv_sa[i]] = max(0, lcp[_inv_sa[i - 1]] - 1); 664 } 665 666 int len = min(n - 1 - i, n - 1 - sa[_inv_sa[i] + 1]); 667 while (lcp[_inv_sa[i]] < len && _s[i + lcp[_inv_sa[i]]] == _s[sa[_inv_sa[i] + 1] + lcp[_inv_sa[i]]]){ 668 lcp[_inv_sa[i]]++; 669 } 670 } 671 } 672 673 int get_lcp(int i, int j){ 674 assert(i != j); 675 i = _inv_sa[i]; 676 j = _inv_sa[j]; 677 if (i > j){ 678 swap(i, j); 679 } 680 j--; 681 return _st_lcp.query(i + 1, j + 1); 682 } 683 }; 684 685 void solve(){ 686 int n, m; 687 cin >> n >> m; 688 string s, t; 689 cin >> s >> t; 690 691 string all = s + "%" + t; 692 SuffixArray suff_array; 693 suff_array.build(all); 694 all += '#'; 695 696 vector<int> from_s; 697 for (int i = 0; i < n + m + 2; i++){ 698 if (suff_array.sa[i] < n){ 699 from_s.push_back(i); 700 } 701 } 702 703 function<pair<int, int>(int, int, char, int)> compare_suff = [&](int start, int pos, char ch, int suff_num){ 704 if (suff_num == 0 || suff_num > n){ 705 return pair<int, int>{1, 0}; 706 } 707 pos -= start; 708 suff_num--; 709 suff_num = suff_array.sa[from_s[suff_num]]; 710 711 int lcp1 = suff_array.get_lcp(suff_num, n + 1 + start); 712 if (lcp1 < pos){ 713 char ch1 = all[suff_num + lcp1]; 714 char ch2 = all[n + 1 + start + lcp1]; 715 if (ch1 < ch2){ 716 return pair<int, int>{1, lcp1}; 717 } 718 else{ 719 return pair<int, int>{-1, lcp1}; 720 } 721 } 722 else if (lcp1 > pos){ 723 char ch1 = all[suff_num + pos]; 724 char ch2; 725 int len = pos; 726 if (ch1 != ch){ 727 ch2 = ch; 728 } 729 else{ 730 len = lcp1; 731 ch1 = all[suff_num + lcp1]; 732 ch2 = all[n + 1 + start + lcp1]; 733 } 734 if (ch1 < ch2){ 735 return pair<int, int>{1, len}; 736 } 737 else{ 738 return pair<int, int>{-1, len}; 739 } 740 } 741 742 char ch1 = all[suff_num + lcp1]; 743 char ch2 = ch; 744 if (ch1 < ch2){ 745 return pair<int, int>{1, pos}; 746 } 747 else if (ch1 > ch2){ 748 return pair<int, int>{-1, pos}; 749 } 750 751 int lcp2 = suff_array.get_lcp(suff_num + lcp1 + 1, n + 1 + start + lcp1 + 1); 752 753 ch1 = all[suff_num + lcp1 + 1 + lcp2]; 754 ch2 = all[n + 1 + start + lcp1 + 1 + lcp2]; 755 756 if (ch1 < ch2){ 757 return pair<int, int>{1, pos + 1 + lcp2}; 758 } 759 else{ 760 return pair<int, int>{-1, pos + 1 + lcp2}; 761 } 762 }; 763 764 function<int(int, int, char)> get_max_len = [&](int start, int pos, char ch){ 765 int suff_len = n + 1 + start; 766 767 int l = 0, r = from_s.size(); 768 while(l <= r){ 769 int m = l + (r - l) / 2; 770 if (compare_suff(start, pos, ch, m).first == -1){ 771 r = m - 1; 772 } 773 else{ 774 l = m + 1; 775 } 776 } 777 int res = 0; 778 res = max(res, compare_suff(start, pos, ch, l - 1).second); 779 res = max(res, compare_suff(start, pos, ch, l).second); 780 return res; 781 }; 782 783 int ans = 0; 784 int start = 0; 785 int pred = -1; 786 787 for (int i = 0; i < m; i++){ 788 int mx_len = 0; 789 for (char ch = 'a'; ch <= 'z'; ch++){ 790 mx_len = max(mx_len, get_max_len(start, i, ch)); 791 } 792 pred = max(pred, mx_len); 793 if (mx_len < i - start + 1){ 794 ans++; 795 start += pred; 796 pred = -1; 797 i = start - 1; 798 continue; 799 } 800 } 801 if (start != m){ 802 ans++; 803 } 804 805 cout << ans << '\n'; 806 } 807 808 signed main() 809 { 810 #ifdef FELIX 811 auto _clock_start = chrono::high_resolution_clock::now(); 812 #endif 813 ios_base::sync_with_stdio(false); 814 cin.tie(0); 815 cout.tie(0); 816 817 int t = 1; 818 cin >> t; 819 while(t--){ 820 solve(); 821 } 822 823 #ifdef FELIX 824 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 825 chrono::high_resolution_clock::now() 826 - _clock_start).count() << "ms." << endl; 827 #endif 828 return 0; 829 } 830 ``` 831 832 [2196F - Indivisible](/contest/2196/problem/F "Codeforces Round 1079 (Div. 1)") 833 834 **Tutorial** 835 836 Tutorial is loading... 837 838 **Solution** 839 840 ``` 841 #include <bits/stdc++.h> 842 843 #define int long long 844 #define pb push_back 845 #define all(x) x.begin(), (x).end() 846 #define rall(x) x.rbegin(), (x).rend() 847 using namespace std; 848 849 vector<pair<int, int>> theSolve(int n, int m) { 850 if (m == 1 || m == 2 || m == 4 || m == 6) { 851 return {}; 852 } 853 if (m == 12) { 854 vector<pair<int, int>> e; 855 for (int x = 1; x <= 6; x++) { 856 for (int y = x + 1; y <= 6; y++) { 857 if (max(x, y) >= 4) { 858 e.pb({x, y}); 859 } 860 } 861 } 862 return e; 863 } 864 if (n == 6 && m == 11) { 865 return {{1, 2}, 866 {1, 3}, 867 {2, 4}, 868 {2, 5}, 869 {2, 6}, 870 {3, 4}, 871 {3, 5}, 872 {3, 6}, 873 {4, 5}, 874 {4, 6}, 875 {5, 6}}; 876 } 877 if (n == 8 && m == 22) { 878 vector<pair<int, int>> e; 879 for (int v = 1; v <= 7; v++) { 880 for (int u = v + 1; u <= 7; u++) { 881 e.pb({v, u}); 882 } 883 } 884 e.pb({7, 8}); 885 return e; 886 } 887 if (n == 10 && m == 39) { 888 vector<pair<int, int>> e; 889 for (int x = 1; x <= n - 1; x++) { 890 for (int y = x + 1; y <= n - 1; y++) { 891 e.pb({x, y}); 892 } 893 } 894 for (int x = 1; x <= 3; x++) { 895 e.pb({n, x}); 896 } 897 return e; 898 } 899 vector<pair<int, int>> edges; 900 if (n % 2 == 1) { 901 while (m <= (n - 2) * (n - 3) / 2) { 902 n -= 2; 903 } 904 int q = (2 * m) / n, r = (2 * m) % n; 905 if (q % 2 == 0) { 906 for (int v = 0; v < n; v++) { 907 for (int p = 0; p < q / 2; p++) { 908 int u = (v + 1 + p) % n; 909 edges.pb({v + 1, u + 1}); 910 } 911 } 912 for (int v = 0; v < r / 2; v++) { 913 edges.pb({v + 1, (v + n / 2) % n + 1}); 914 } 915 } else { 916 int d = (n - r) / 2; 917 for (int v = 0; v < n; v++) { 918 for (int p = 0; p < (q + 1) / 2; p++) { 919 if (v % 2 == 0 && p == 0 && d) { 920 d--; 921 continue; 922 } 923 int u = (v + 1 + p) % n; 924 edges.pb({v + 1, u + 1}); 925 } 926 } 927 } 928 return edges; 929 } 930 931 int rest = n * (n - 1) / 2 - m; 932 if (rest == 0 || rest == 1 || rest == 2 || rest == 4 || rest == 6) { 933 return {}; 934 } 935 if (m <= (n - 1) * (n - 2) / 2) { 936 return theSolve(n - 1, m); 937 } 938 vector<pair<int, int>> inv_e = theSolve(n - 1, n * (n - 1) / 2 - m); 939 for (auto &p : inv_e) { 940 if (p.first > p.second) { 941 swap(p.first, p.second); 942 } 943 } 944 sort(all(inv_e)); 945 int i = 0; 946 vector<pair<int, int>> e; 947 for (int v = 1; v <= n; v++) { 948 for (int u = v + 1; u <= n; u++) { 949 if (i < (int) inv_e.size() && inv_e[i] == (pair<int, int>) {v, u}) { 950 i++; 951 continue; 952 } 953 e.pb({v, u}); 954 } 955 } 956 return e; 957 } 958 959 void solve() { 960 int n, m; 961 cin >> n >> m; 962 vector<pair<int, int>> e = theSolve(n, m); 963 if (e.empty()) { 964 cout << "No\n"; 965 } else { 966 cout << "Yes\n"; 967 for (auto &[a, b] : e) { 968 cout << a << ' ' << b << '\n'; 969 } 970 } 971 } 972 973 signed main() { 974 ios::sync_with_stdio(false); 975 cin.tie(nullptr); 976 cout.tie(nullptr); 977 int t; 978 cin >> t; 979 while (t--) { 980 solve(); 981 } 982 } 983 ``` 984 985 For those who come after.