1656.md (19712B)
1 Source: https://codeforces.com/blog/entry/101211 2 3 [1656A - Good Pairs](/contest/1656/problem/A) 4 5 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while(t--) { 22 int n; 23 cin >> n; 24 int minv = 1e9+1; 25 int maxv = -1; 26 int mini; 27 int maxi; 28 for(int i=0; i < n; ++i) { 29 int a; 30 cin >> a; 31 if(a > maxv) { 32 maxi = i+1; 33 maxv = a; 34 } 35 if(a < minv) { 36 mini = i+1; 37 minv = a; 38 } 39 } 40 cout << mini << " " << maxi << endl; 41 } 42 43 } 44 ``` 45 46 [1656B - Subtract Operation](/contest/1656/problem/B) 47 48 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [xpov1LL](/profile/xpov1LL "Candidate Master xpov1LL") 49 50 **Solution** 51 52 Tutorial is loading... 53 54 **Code** 55 56 ``` 57 #include<iostream> 58 #include<vector> 59 #include<algorithm> 60 using namespace std; 61 62 int main() { 63 int t; 64 cin >> t; 65 while(t--) { 66 int n, a; 67 cin >> n >> a; 68 vector<int> v(n); 69 for(int& x : v) cin >> x; 70 bool ans = false; 71 if(n == 1) ans = (v[0] == a); 72 else { 73 sort(v.begin(), v.end()); 74 int i = 0; 75 int j = 1; 76 while(j < n and i < n) { 77 if(v[i] + abs(a) == v[j]) { 78 ans = true; 79 break; 80 } 81 else if(v[i] + abs(a) < v[j]) ++i; 82 else ++j; 83 } 84 } 85 cout << (ans? "YES" : "NO") << '\n'; 86 } 87 } 88 ``` 89 90 [1656C - Make Equal With Mod](/contest/1656/problem/C) 91 92 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 93 94 **Solution** 95 96 Tutorial is loading... 97 98 **Code** 99 100 ``` 101 #include<bits/stdc++.h> 102 103 using namespace std; 104 105 typedef vector<int> vi; 106 107 108 int main() { 109 int t; 110 cin >> t; 111 while(t--) { 112 int n; 113 cin >> n; 114 vi a(n); 115 for(int i=0; i < n; ++i) cin >> a[i]; 116 sort(a.begin(), a.end()); 117 bool one = false; 118 bool consec = false; 119 for(int i=0; i < n; ++i) { 120 if(a[i] == 1) one = true; 121 if(i < n-1 && a[i]+1 == a[i+1]) consec = true; 122 } 123 124 cout << ((one && consec) ? "NO" : "YES") << endl; 125 } 126 127 } 128 ``` 129 130 [1656D - K-good](/contest/1656/problem/D) 131 132 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 133 134 **Solution** 135 136 Tutorial is loading... 137 138 **Code** 139 140 ``` 141 #include<bits/stdc++.h> 142 143 using namespace std; 144 145 #define endl '\n' 146 147 typedef long long ll; 148 149 int main() { 150 ios::sync_with_stdio(false); 151 int T; 152 cin >> T; 153 while(T--) { 154 ll n; 155 cin >> n; 156 ll x = n; 157 while(x % 2 == 0) x /= 2; 158 if(x == 1) { 159 cout << -1 << endl; 160 } 161 else if(x <= 2e9 && (x*(x+1))/2 <= n) { 162 cout << x << endl; 163 } 164 else { 165 cout << 2*(n/x) << endl; 166 } 167 } 168 } 169 ``` 170 171 [1656E - Equal Tree Sums](/contest/1656/problem/E) 172 173 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 174 175 **Solution** 176 177 Tutorial is loading... 178 179 **Code** 180 181 ``` 182 #include<bits/stdc++.h> 183 184 using namespace std; 185 186 typedef vector<int> vi; 187 typedef vector<vi> vvi; 188 189 vvi al; 190 vi ans; 191 192 void dfs(int u, int p, int c) { 193 ans[u] = ((int)al[u].size())*c; 194 for(int v : al[u]) { 195 if(v != p) { 196 dfs(v, u, -c); 197 } 198 } 199 } 200 201 int main() { 202 int T; 203 cin >> T; 204 while(T--) { 205 int n; 206 cin >> n; 207 al = vvi(n); 208 for(int i=0; i < n-1; ++i) { 209 int u, v; 210 cin >> u >> v; 211 u--; 212 v--; 213 al[u].push_back(v); 214 al[v].push_back(u); 215 } 216 ans = vi(n); 217 dfs(0, -1, 1); 218 for(int i=0; i < n; ++i) { 219 cout << ans[i]; 220 if(i < n-1) cout << " "; 221 } 222 cout << endl; 223 } 224 } 225 ``` 226 227 [1656F - Parametric MST](/contest/1656/problem/F) 228 229 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 230 231 **Solution** 232 233 Tutorial is loading... 234 235 **Code** 236 237 ``` 238 #include<bits/stdc++.h> 239 240 using namespace std; 241 242 typedef long long ll; 243 typedef vector<ll> vi; 244 245 int main() { 246 int T; 247 cin >> T; 248 while(T--) { 249 ll n; 250 cin >> n; 251 vi a(n); 252 ll tsum = 0; 253 for(int i=0; i < n; ++i) { 254 cin >> a[i]; 255 tsum += a[i]; 256 } 257 sort(a.begin(), a.end()); 258 if(a[n-1]*(n-2) + tsum < 0 || a[0]*(n-2) + tsum > 0) { 259 cout << "INF" << endl; 260 continue; 261 } 262 263 ll cslope = a[n-1]*(n-2) + tsum; 264 ll cvalue = -(n-1)*a[n-1]*a[n-1]; 265 266 267 ll ans = cvalue; 268 for(ll i=1; i < n; ++i) { 269 ll d = a[n-i]-a[n-i-1]; 270 cvalue += cslope*d; 271 ans = max(cvalue, ans); 272 273 cslope += a[0]-a[n-1]; 274 275 } 276 cout << ans << endl; 277 } 278 } 279 ``` 280 281 [1656G - Cycle Palindrome](/contest/1656/problem/G) 282 283 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 284 285 **Solution** 286 287 Tutorial is loading... 288 289 **Code** 290 291 ``` 292 #include<bits/stdc++.h> 293 294 using namespace std; 295 296 typedef vector<int> vi; 297 typedef vector<vi> vvi; 298 299 vi obtain_p_permutation(const vi& a) { 300 int n = a.size(); 301 vi pp(n, -1); 302 vi p(n); 303 int cp = 0; 304 vi cnt(n); 305 for(int i=0; i < n; ++i) { 306 cnt[a[i]]++; 307 } 308 for(int i=0; i < n; ++i) { 309 if(pp[a[i]] == -1) { 310 if(cnt[a[i]] == 1) { 311 p[i] = n/2; 312 } 313 else { 314 p[i] = cp; 315 pp[a[i]] = n-cp-1; 316 cp++; 317 cnt[a[i]]--; 318 } 319 } 320 else { 321 p[i] = pp[a[i]]; 322 pp[a[i]] = -1; 323 cnt[a[i]]--; 324 } 325 } 326 return p; 327 } 328 329 vvi find_cycles(vi p, vi& in_cyc) { 330 int n = p.size(); 331 vi vis = vi(n); 332 vvi cycles; 333 for(int i=0; i < n; ++i) { 334 if(!vis[i]) { 335 vi cyc; 336 int v = i; 337 while(!vis[v]) { 338 cyc.push_back(v); 339 in_cyc[v] = cycles.size(); 340 vis[v] = true; 341 v = p[v]; 342 } 343 cycles.push_back(cyc); 344 } 345 } 346 return cycles; 347 } 348 349 int find_set(vi& dsu, int x) { 350 if(dsu[x] == x) return x; 351 return dsu[x] = find_set(dsu, dsu[x]); 352 } 353 354 void solve() { 355 int n; 356 cin >> n; 357 vi a(n); 358 vi cnt(n); 359 for(int i=0; i < n; ++i) { 360 cin >> a[i]; 361 a[i]--; 362 cnt[a[i]]++; 363 } 364 int odd_i = -1; 365 for(int i=0; i < n; ++i) { 366 if(cnt[i]%2 == 1) { 367 if(odd_i == -1) { 368 odd_i = i; 369 } 370 else { 371 odd_i = -2; 372 } 373 } 374 } 375 if(odd_i == -2) { 376 cout << "NO" << endl; 377 } 378 else if(odd_i != -1 && (cnt[odd_i] == 1 && odd_i == a[n/2])) { 379 cout << "NO" << endl; 380 } 381 else { 382 383 vi p = obtain_p_permutation(a); 384 if(odd_i != -1 && p[n/2] == n/2) { 385 for(int i=0; i < n; ++i) { 386 if(i != n/2 && a[i] == odd_i) { 387 p[n/2] = p[i]; 388 p[i] = n/2; 389 break; 390 } 391 } 392 } 393 vi rp(n); 394 for(int i=0; i < n; ++i) { 395 rp[p[i]] = i; 396 } 397 vvi cycles; 398 vi in_cyc(n); 399 cycles = find_cycles(p, in_cyc); 400 401 vi dsu(n); 402 for(int i=0; i < n; ++i) dsu[i] = i; 403 for(int i=0; i < n; ++i) { 404 if(find_set(dsu, in_cyc[i]) != find_set(dsu, in_cyc[n-i-1])) { 405 dsu[find_set(dsu, in_cyc[i])] = find_set(dsu, in_cyc[n-i-1]); 406 int j1 = rp[i]; 407 int j2 = rp[n-i-1]; 408 p[j2] = i; 409 rp[i] = j2; 410 p[j1] = n-i-1; 411 rp[n-i-1] = j1; 412 } 413 } 414 cycles = find_cycles(p, in_cyc); 415 int nc = cycles.size(); 416 417 418 vi prev_p = vi(p); 419 vi prev_rp = vi(rp); 420 421 for(int i=0; i < nc-1; ++i) { 422 int i0 = cycles[i][0]; 423 int ip1 = cycles[(i+1)][0]; 424 p[prev_rp[n-i0-1]] = ip1; 425 rp[ip1] = prev_rp[n-i0-1]; 426 } 427 p[prev_rp[n-cycles[nc-1][0]-1]] = n-cycles[0][0]-1; 428 rp[n-cycles[0][0]-1] = prev_rp[n-cycles[nc-1][0]-1]; 429 for(int i=0; i < nc-1; ++i) { 430 int i0 = cycles[i][0]; 431 int ip1 = cycles[(i+1)][0]; 432 p[prev_rp[i0]] = n-ip1-1; 433 rp[n-ip1-1] = prev_rp[i0]; 434 } 435 p[prev_rp[cycles[nc-1][0]]] = cycles[0][0]; 436 rp[cycles[0][0]] = prev_rp[cycles[nc-1][0]]; 437 438 cout << "YES" << endl; 439 for(int i=0; i < n; ++i) { 440 cout << rp[i]+1 << " "; 441 } 442 cout << endl; 443 444 } 445 446 447 } 448 449 int main() { 450 int T; 451 cin >> T; 452 while(T--) { 453 solve(); 454 } 455 } 456 ``` 457 458 [1656H - Equal LCM Subsets](/contest/1656/problem/H) 459 460 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 461 462 **Solution** 463 464 Tutorial is loading... 465 466 **Code** 467 468 ``` 469 #include<bits/stdc++.h> 470 471 using namespace std; 472 473 typedef __int128 ll; 474 typedef vector<ll> vi; 475 typedef vector<vi> vvi; 476 477 478 ll read_ll() { 479 string s; 480 cin >> s; 481 ll x = 0; 482 for(int i=0; i < (int)s.length(); ++i) { 483 x *= 10; 484 x += ll(s[i]-'0'); 485 } 486 return x; 487 } 488 489 void print_ll(ll x) { 490 vector<int> p; 491 while(x > 0) { 492 p.push_back((int)(x%10)); 493 x /= 10; 494 } 495 reverse(p.begin(), p.end()); 496 for(int y : p) cout << y; 497 } 498 499 inline ll ctz(ll x) { 500 long long a = x&((ll(1)<<ll(63))-ll(1)); 501 long long b = x>>ll(63); 502 if(a == 0) return ll(63)+__builtin_ctzll(b); 503 return __builtin_ctzll(a); 504 } 505 506 inline ll abll(ll x) { 507 return x >= 0 ? x : -x; 508 } 509 510 ll gcd(ll a, ll b) { 511 if(b == 0) return a; 512 if(a == 0) return b; 513 514 int az = ctz(a); 515 int bz = ctz(b); 516 int shift = min(az, bz); 517 b >>= bz; 518 519 while(a != 0) { 520 a >>= az; 521 ll diff = b-a; 522 if(diff) az = ctz(diff); 523 b = min(a, b); 524 a = abll(diff); 525 } 526 return b << shift; 527 } 528 529 void init_st(vi& st, const vi& v) { 530 int n = v.size(); 531 for(int i=0; i < n; ++i) { 532 st[n+i] = v[i]; 533 } 534 for(int i=n-1; i >= 1; --i) { 535 st[i] = gcd(st[2*i], st[2*i+1]); 536 } 537 } 538 539 void update_st(vi& st, int i, ll x) { 540 int n = (int)st.size() / 2; 541 int pos = n+i; 542 st[pos] = x; 543 while(pos > 1) { 544 pos /= 2; 545 st[pos] = gcd(st[2*pos], st[2*pos+1]); 546 } 547 } 548 549 void solve(const vi& a, const vi& b, vector<bool>& ai, vector<bool>& bi) { 550 int n = a.size(); 551 int m = b.size(); 552 vvi st_a = vvi(n, vi(2*m, 0)); 553 vvi st_b = vvi(m, vi(2*n, 0)); 554 for(int i=0; i < n; ++i) { 555 vi af(m); 556 for(int j=0; j < m; ++j) { 557 af[j] = a[i]/gcd(a[i], b[j]); 558 } 559 init_st(st_a[i], af); 560 } 561 for(int i=0; i < m; ++i) { 562 vi bf(n); 563 for(int j=0; j < n; ++j) { 564 bf[j] = b[i]/gcd(b[i], a[j]); 565 } 566 init_st(st_b[i], bf); 567 } 568 queue<int> dq; 569 for(int i=0; i < n; ++i) { 570 if(st_a[i][1] > 1) { 571 dq.push(i); 572 ai[i] = false; 573 } 574 } 575 for(int i=0; i < m; ++i) { 576 if(st_b[i][1] > 1) { 577 dq.push(n+i); 578 bi[i] = false; 579 } 580 } 581 while(!dq.empty()) { 582 int idx = dq.front(); 583 dq.pop(); 584 if(idx < n) { 585 int i = idx; 586 for(int j=0; j < m; ++j) { 587 if(bi[j]) { 588 update_st(st_b[j], i, b[j]); 589 if(st_b[j][1] > 1) { 590 dq.push(n+j); 591 bi[j] = false; 592 } 593 } 594 } 595 } 596 else { 597 int i = idx-n; 598 for(int j=0; j < n; ++j) { 599 if(ai[j]) { 600 update_st(st_a[j], i, a[j]); 601 if(st_a[j][1] > 1) { 602 dq.push(j); 603 ai[j] = false; 604 } 605 } 606 } 607 } 608 } 609 610 } 611 612 613 614 int main() { 615 int T; 616 cin >> T; 617 while(T--) { 618 int n, m; 619 cin >> n >> m; 620 vi a(n); 621 vi b(m); 622 for(int i=0; i < n; ++i) a[i] = read_ll(); 623 for(int i=0; i < m; ++i) b[i] = read_ll(); 624 vector<bool> ai(n, true); 625 vector<bool> bi(m, true); 626 solve(a, b, ai, bi); 627 int as = 0; 628 int bs = 0; 629 for(int i=0; i < n; ++i) { 630 if(ai[i]) as++; 631 } 632 for(int i=0; i < m; ++i) { 633 if(bi[i]) bs++; 634 } 635 if(as == 0 || bs == 0) cout << "NO" << endl; 636 else { 637 cout << "YES" << endl; 638 cout << as << " " << bs << endl; 639 for(int i=0; i < n; ++i) { 640 if(ai[i]) { 641 print_ll(a[i]); 642 cout << " "; 643 } 644 } 645 cout << endl; 646 for(int i=0; i < m; ++i) { 647 if(bi[i]) { 648 print_ll(b[i]); 649 cout << " "; 650 } 651 } 652 cout << endl; 653 654 655 } 656 } 657 } 658 ``` 659 660 [1656I - Neighbour Ordering](/contest/1656/problem/I) 661 662 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP") 663 664 **Solution** 665 666 Tutorial is loading... 667 668 **Code** 669 670 ``` 671 #include<bits/stdc++.h> 672 673 using namespace std; 674 675 typedef vector<int> vi; 676 typedef vector<vi> vvi; 677 typedef pair<int, int> ii; 678 typedef vector<ii> vii; 679 typedef vector<vii> vvii; 680 681 struct graph { 682 int n; 683 int m; 684 685 vvi al; 686 vi morphism; 687 688 vvi dfs_children; 689 vi dfs_parent; 690 vi dfs_num; 691 vi dfs_low; 692 int dfs_count; 693 694 bool is_root_ac = false; 695 696 bool bad_biccon = false; 697 vii repr_edge; 698 699 void dt_dfs(int v, int par) { 700 dfs_parent[v] = par; 701 dfs_num[v] = dfs_low[v] = dfs_count++; 702 for(int u : al[v]) { 703 if(u == par) { 704 //Nothing 705 } 706 else if(dfs_num[u] == -1) { 707 dfs_children[v].push_back(u); 708 dt_dfs(u, v); 709 dfs_low[v] = min(dfs_low[v], dfs_low[u]); 710 } 711 else { 712 dfs_low[v] = min(dfs_low[v], dfs_num[u]); 713 } 714 } 715 } 716 717 ii min_repr_edge(ii a, ii b) { 718 if(a.first == -1) return b; 719 if(b.first == -1) return a; 720 if(dfs_num[a.second] < dfs_num[b.second]) return a; 721 if(dfs_num[a.second] > dfs_num[b.second]) return b; 722 if(dfs_num[a.first] > dfs_num[b.first]) return a; 723 if(dfs_num[a.first] < dfs_num[b.first]) return b; 724 return a; 725 } 726 727 void dt_dfs_hamil(int v) { 728 repr_edge[v] = ii(-1, -1); 729 730 for(int u : dfs_children[v]) { 731 dt_dfs_hamil(u); 732 repr_edge[v] = min_repr_edge(repr_edge[v], repr_edge[u]); 733 } 734 735 for(int u : al[v]) { 736 if(u == dfs_parent[v]) { 737 //Nothing 738 } 739 else if(dfs_num[u] < dfs_num[v]) { 740 repr_edge[v] = min_repr_edge(repr_edge[v], ii(v, u)); 741 } 742 743 } 744 745 if(dfs_parent[v] == -1) { 746 //Root case 747 748 //Nothing more to check, repr_edge will always be set correctly. 749 } 750 else { 751 if(dfs_children[v].size() == 0) { 752 //Nothing to check 753 } 754 else if(dfs_children[v].size() == 1) { 755 //Lemma 4 756 if(dfs_low[dfs_children[v][0]] != dfs_low[v] && dfs_low[dfs_children[v][0]] != dfs_num[dfs_parent[v]]) { 757 bad_biccon = true; 758 } 759 } 760 else if(dfs_children[v].size() == 2) { 761 //Lemma 3 762 if(dfs_parent[dfs_parent[v]] != -1) { 763 if(!((dfs_low[dfs_children[v][0]] == dfs_num[dfs_parent[v]]) ^ (dfs_low[dfs_children[v][1]] == dfs_num[dfs_parent[v]]))) { 764 bad_biccon = true; 765 } 766 } 767 if(dfs_low[v] < min(dfs_low[dfs_children[v][0]], dfs_low[dfs_children[v][1]])) { 768 bad_biccon = true; 769 } 770 } 771 else { 772 bad_biccon = true; 773 } 774 } 775 } 776 777 void dt_dfs_cedges(vvii& cedges, vii& edge_stack, int v, int par) { 778 dfs_parent[v] = par; 779 dfs_num[v] = dfs_low[v] = dfs_count++; 780 for(int u : al[v]) { 781 if(u == par) { 782 //Nothing 783 } 784 else if(dfs_num[u] == -1) { 785 dfs_children[v].push_back(u); 786 edge_stack.emplace_back(v, u); 787 dt_dfs_cedges(cedges, edge_stack, u, v); 788 dfs_low[v] = min(dfs_low[v], dfs_low[u]); 789 790 if((par == -1 && is_root_ac) || (par != -1 && dfs_low[u] >= dfs_num[v])) { 791 vii comp; 792 while(edge_stack.back().first != v || edge_stack.back().second != u) { 793 comp.push_back(edge_stack.back()); 794 edge_stack.pop_back(); 795 } 796 comp.push_back(edge_stack.back()); 797 edge_stack.pop_back(); 798 cedges.push_back(comp); 799 } 800 } 801 else { 802 dfs_low[v] = min(dfs_low[v], dfs_num[u]); 803 if(dfs_num[u] < dfs_num[v]) { 804 edge_stack.emplace_back(v, u); 805 } 806 } 807 } 808 } 809 810 void generate_dfs_tree(int root) { 811 dfs_children = vvi(n, vi()); 812 dfs_parent = vi(n); 813 dfs_count = 0; 814 dfs_num = vi(n, -1); 815 dfs_low = vi(n, -1); 816 dt_dfs(root, -1); 817 } 818 819 void generate_edge_partition(vvii& cedges, vii& edge_stack, int root) { 820 generate_dfs_tree(root); 821 is_root_ac = (dfs_children[root].size() > 1); 822 823 dfs_children = vvi(n, vi()); 824 dfs_parent = vi(n); 825 dfs_count = 0; 826 dfs_num = vi(n, -1); 827 dfs_low = vi(n, -1); 828 dt_dfs_cedges(cedges, edge_stack, root, -1); 829 if(!edge_stack.empty()) cedges.push_back(edge_stack); 830 } 831 832 void generate_hamil_dfs_tree(int root) { 833 generate_dfs_tree(root); 834 repr_edge = vii(n, ii()); 835 dt_dfs_hamil(root); 836 } 837 }; 838 839 vector<graph> partition_biconnected(graph& g) { 840 vvii cedges; 841 vii edge_stack; 842 g.generate_edge_partition(cedges, edge_stack, 0); 843 vector<graph> comp; 844 for(vii& vec : cedges) { 845 graph h; 846 h.n = 0; 847 h.m = vec.size(); 848 unordered_map<int, int> rmorph; 849 for(ii e : vec) { 850 if(rmorph.find(e.first) == rmorph.end()) { 851 rmorph[e.first] = h.n++; 852 } 853 if(rmorph.find(e.second) == rmorph.end()) { 854 rmorph[e.second] = h.n++; 855 } 856 } 857 h.morphism = vi(h.n); 858 h.al = vvi(h.n); 859 for(ii e : vec) { 860 int u = rmorph[e.first]; 861 int v = rmorph[e.second]; 862 h.morphism[u] = g.morphism[e.first]; 863 h.morphism[v] = g.morphism[e.second]; 864 h.al[u].push_back(v); 865 h.al[v].push_back(u); 866 } 867 comp.push_back(h); 868 } 869 return comp; 870 } 871 872 void upwards_path(graph& g, vi& hc, int v, int tar); 873 874 void downwards_path(graph& g, vi& hc, int v, int tar); 875 876 void upwards_path(graph& g, vi& hc, int v, int tar) { 877 if(g.dfs_children[v].size() == 2) { 878 int u1 = g.dfs_children[v][0]; 879 int u2 = g.dfs_children[v][1]; 880 if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2); 881 hc.push_back(v); 882 downwards_path(g, hc, u1, g.repr_edge[u1].first); 883 if(v != tar) { 884 upwards_path(g, hc, g.dfs_parent[v], tar); 885 } 886 } 887 else if(g.dfs_children[v].size() == 1) { 888 int u = g.dfs_children[v][0]; 889 hc.push_back(v); 890 if(g.repr_edge[u] != g.repr_edge[v]) { 891 downwards_path(g, hc, u, g.repr_edge[u].first); 892 } 893 if(v != tar) { 894 upwards_path(g, hc, g.dfs_parent[v], tar); 895 } 896 } 897 else { 898 hc.push_back(v); 899 if(v != tar) { 900 upwards_path(g, hc, g.dfs_parent[v], tar); 901 } 902 } 903 } 904 905 void downwards_path(graph& g, vi& hc, int v, int tar) { 906 if(g.dfs_children[v].size() == 2) { 907 int u1 = g.dfs_children[v][0]; 908 int u2 = g.dfs_children[v][1]; 909 if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2); 910 upwards_path(g, hc, g.repr_edge[u1].first, u1); 911 hc.push_back(v); 912 downwards_path(g, hc, u2, tar); 913 } 914 else if(g.dfs_children[v].size() == 1) { 915 int u = g.dfs_children[v][0]; 916 if(v == tar) { 917 upwards_path(g, hc, g.repr_edge[u].first, u); 918 hc.push_back(v); 919 } 920 else { 921 hc.push_back(v); 922 downwards_path(g, hc, u, tar); 923 } 924 } 925 else { 926 hc.push_back(v); 927 } 928 } 929 930 vi hamiltonian_cycle(graph& g) { 931 g.generate_hamil_dfs_tree(0); 932 if(g.bad_biccon) return vi(); 933 vi hc; 934 downwards_path(g, hc, 0, g.repr_edge[0].first); 935 assert((int)hc.size() == g.n); 936 return hc; 937 } 938 939 int comp_index; 940 bool cyclic_comparator(int a, int b) { 941 if(a < comp_index) a += 1e7; 942 if(b < comp_index) b += 1e7; 943 return a < b; 944 } 945 946 graph sort_graph(const graph& g, const vi& hc) { 947 graph h; 948 h.n = g.n; 949 h.m = g.m; 950 h.morphism = vi(g.n); 951 h.al = vvi(g.n); 952 vi rhc(g.n); 953 for(int i=0; i < g.n; ++i) { 954 h.morphism[i] = g.morphism[hc[i]]; 955 rhc[hc[i]] = i; 956 } 957 for(int i=0; i < g.n; ++i) { 958 for(int j : g.al[hc[i]]) { 959 h.al[i].push_back(rhc[j]); 960 } 961 comp_index = i; 962 //This is m log m, can be improved 963 sort(h.al[i].begin(), h.al[i].end(), cyclic_comparator); 964 } 965 return h; 966 } 967 968 bool has_crossing(const graph& g) { 969 vii bad_stack; 970 for(int i=0; i < g.n; ++i) { 971 comp_index = i; 972 while(!bad_stack.empty() && i == bad_stack.back().first) bad_stack.pop_back(); 973 for(int j=(int)g.al[i].size()-2; j > 0; --j) { 974 int u = g.al[i][j]; 975 if(!bad_stack.empty() && cyclic_comparator(bad_stack.back().first, u) && cyclic_comparator(u, bad_stack.back().second)) { 976 return true; 977 } 978 if(u > i && (bad_stack.empty() || u != bad_stack.back().first)) { 979 bad_stack.emplace_back(u, i); 980 } 981 } 982 } 983 return false; 984 } 985 986 void merge_ans(const graph& g, vvi& ans) { 987 for(int i=0; i < g.n; ++i) { 988 for(int j : g.al[i]) { 989 ans[g.morphism[i]].push_back(g.morphism[j]); 990 } 991 } 992 } 993 994 void merge_single_edge_ans(const graph& g, vvi& ans) { 995 int u = g.morphism[0]; 996 int v = g.morphism[1]; 997 ans[u].push_back(v); 998 ans[v].push_back(u); 999 } 1000 1001 vvi solve(graph& input_graph) { 1002 vvi ans(input_graph.n); 1003 vector<graph> components = partition_biconnected(input_graph); 1004 for(graph g : components) { 1005 if(g.n == 1) { 1006 //Nothing 1007 } 1008 else if(g.n == 2) { 1009 merge_single_edge_ans(g, ans); 1010 } 1011 else { 1012 vi hc = hamiltonian_cycle(g); 1013 if(hc.empty()) { 1014 return vvi(); 1015 } 1016 graph g2 = sort_graph(g, hc); 1017 if(has_crossing(g2)) return vvi(); 1018 merge_ans(g2, ans); 1019 } 1020 } 1021 return ans; 1022 } 1023 1024 graph read_graph() { 1025 graph g; 1026 int n, m; 1027 cin >> n >> m; 1028 g.n = n; 1029 g.m = m; 1030 g.al = vvi(n, vi()); 1031 g.morphism = vi(n, 0); 1032 for(int i=0; i < n; ++i) { 1033 g.morphism[i] = i; 1034 } 1035 for(int i=0; i < m; ++i) { 1036 int u, v; 1037 cin >> u >> v; 1038 g.al[u].push_back(v); 1039 g.al[v].push_back(u); 1040 } 1041 return g; 1042 } 1043 1044 void print_ans(const vvi& ans) { 1045 int n = ans.size(); 1046 if(n == 0) { 1047 cout << "NO" << endl; 1048 } 1049 else { 1050 cout << "YES" << endl; 1051 for(int i=0; i < n; ++i) { 1052 for(int x : ans[i]) { 1053 cout << x << " "; 1054 } 1055 cout << endl; 1056 } 1057 } 1058 } 1059 1060 int main() { 1061 int T; 1062 cin >> T; 1063 while(T--) { 1064 graph input_graph = read_graph(); 1065 vvi ans = solve(input_graph); 1066 print_ans(ans); 1067 } 1068 } 1069 ```